mehrere TreeSets so speichern, dass man sie miteinander vergleichen kann

[system.exit]

Hallo,

ich versuche ein kleines Demoprogramm zu schreiben, das einen Greedyalgorithmus auf das Set Cover Problem angewendet, zeigt.

Kurze Erklärung:
man hat eine Obermenge, die aus allen Elementen besteht, die in dazugehörigen Untermengen vorkommen. Man soll aus allen Untermengen eine Auswahl finden, sodass jedes Element der Obermenge mindestens einmal abgedeckt ist.
Beispiel:
Obermenge E = {A, B, C}
Untermenge U1 = {A, B}
Untermenge U2 = {B, C}
Untermenge U3 = {A, C}

=> Obermenge E ist abgedeckt durch U1 und U2.

In meinem Programm soll der User die Möglichkeit haben, zu wählen, ob seine Mengen aus chars oder ints besteht. Dann soll er alle Elemente der Obermenge eingeben. Danach werden so lange Untermengen hinzugefügt, bis er fertig ist, woraufhin das Programm eine mögliche Lösung für die Eingabe ausspuckt.

Mein Ansatz:

• User input durch Scanner
• Da Scanner Input als Array speichert, wird die Eingabe zuerst in ein TreeSet konvertiert. Dadurch werden Duplikate ignoriert und die Eingabe ist geordnet.
• Es ist unbekannt, wie viele Untermengen der User eingeben möchte. Daher sollen so lange Untermengen angelegt und gespeichert werden, bis User sagt "fertig".

Meine Probleme:

• ich glaube, ich überschreibe immer die selbe Untermenge, wenn ich in der Schleife bin, wo der User neue Mengen anlegen kann
• ich weiß nicht, wie ich überhaupt die Obermenge mit nur einer einzigen Untermenge vergleichen könnte
• der Iterator für die While-Schleife ab Zeile 94 funktioniert nicht so, wie ich es gern hätte.

import java.util.Scanner;
import java.util.Set;

/**
 * contains all instructions and interactions with user
 */
public class Instructions {

    public static void instructions() {
        Scanner scan = new Scanner(System.in);

        //Welcome message.
        System.out.println("This is a simple demo of a greedy algorithm for the set cover problem.\n"
                + "Let's get started.\n\n");

        //user instructions: choose which element types (char or int) to use for demo.
        System.out.println("For this application to work, first select which kind of elements your sets will contain.\n"
                + "Press: "
                + "\n"
                + "c \t for CHARACTERS like a, b, c "
                + "\n"
                + "\t\t --- or ---"
                + "\n"
                + "i \t for INTEGERS like -2, 0, 11 \n");

        //use charAt(0) in case user types in more than one symbol
        char elementType = scan.nextLine().toLowerCase().charAt(0);

        //user input should only be 'c' or 'i'. Repeat until input is valid. Not case-sensitive.
        boolean incorrectInput = true;
        while(incorrectInput) {               
            switch  (elementType) {
                case 'c':
                    //user feedback.
                    System.out.println("Your sets will have elements of type CHAR.\n");

                    //user instructions: enter elements for ground set E
                    System.out.println("Please enter all elements that are in the ground set E:\n");

                    //char array that holds user input. Input should be abcd. No spaces or commas as it will also be stored. Improve?
                    char[] inputGroundSet = scan.nextLine().toCharArray();

                    //cast char[] to Character[] for use with convertArrayToTreeSet-Method:
                    Character[] charGroundSetBoxed = new String(inputGroundSet).chars().mapToObj(c -> (char) c).toArray(Character[]::new);

                    //convert the Array to a Set:
                    Set <Character> groundSet = HelperMethods.convertArrayToTreeSet(charGroundSetBoxed);

                    //user feedback. Prints out sorted set without duplicates.
                    System.out.println("The elements in your ground set are: " + groundSet);

                    //set to false to leave while-loop.
                    incorrectInput = false;
                    break;

                case 'i':
                    //TODO do the same with integers.

                    System.out.println("THIS IS A PINK ELEFANT. Not implemented yet.");

                    //set to false to leave while-loop
                    incorrectInput = false;
                    break;

                default:
                    System.out.println("Not a valid option.\n"
                            + "Please type 'c' for characters or 'i' for integers.");

                    //keep scanning until input is valid
                    elementType = scan.nextLine().toLowerCase().charAt(0);
            }
        }


        //conditions for subsets depending on elementType.
        if(elementType == 'c') {
            //user instructions: menu for setting up subsets: new, finish. Cancel would be gth.
            System.out.println("\n\nNow, let's define some subsets.\n"
                    + "Press:"
                    + "\n"
                    + "n\tfor a NEW subset"
                    + "\n"
                    + "\t\t --- or ---"
                    + "\n"
                    + "f\tto FINISH setting up subsets and have covering sets calculated.\n");

            //use charAt(0) in case user types in more than one symbol
            char menu = scan.nextLine().toLowerCase().charAt(0);

            boolean notMenu = true;

            //iterator doesn't work like intended.
            int i = 0;
            while(notMenu) {   
                i++;
                switch (menu) {
                    case 'n':

                        //user instructions: enter elements for current subset
                        //TODO needs to count which subset this is.
                        System.out.println("Please enter all elements that are in subset S" + i + ":\n");

                        //char array that holds user input. Input should be abcd. No spaces or commas as it will also be stored.
                        char[] inputSubset = scan.nextLine().toCharArray();

                        //cast char[] to Character[] for use with convertArrayToTreeSet-Method:
                        Character[] charSubsetBoxed = new String(inputSubset).chars().mapToObj(c -> (char) c).toArray(Character[]::new);

                        //convert the Array to a Set:
                        Set <Character> subset = HelperMethods.convertArrayToTreeSet(charSubsetBoxed);

                        //user feedback. Prints out sorted set without duplicates.
                        //TODO count which subset
                        System.out.println("The elements in Subset are: " + subset);

                        //set to false to leave while-loop.
                        //notMenu = false;
                        break;

                    case 'f':
                        //TODO do the same with integers.

                        System.out.println("THIS IS A PINK ELEFANT.");

                        //set to false to leave while-loop
                        notMenu = false;
                        break;

                    default:
                        System.out.println("Not a valid option.\n"
                                + "Press n or f.");

                        //keep scanning until input is valid
                        menu = scan.nextLine().toLowerCase().charAt(0);
                }
            }
        }else {
            System.out.println("elementType is not c");
        }
    }

}

import java.util.Set;
import java.util.TreeSet;

public class HelperMethods {
    /**
     * Generic function to convert any Array to a TreeSet (a sorted set without duplicates).
     * Needs casting on primitive data types before use.
     *
     * @param <T>        expected class of the value, e.g. Set <Character> nameOfSet
     * @param array        expected parameter (Scanner stores user input as array)
     * @return            the resulting TreeSet of the arguments in array
     */
    public static <T> Set<T> convertArrayToTreeSet(T array[]) {
        //create empty Set:
        Set <T> treeSet = new TreeSet<>();
        
        //iterate through array and add each element into the set
        for (T t: array) {
            treeSet.add(t);
        }
        
        return treeSet;
    }

}

Wäre super, wenn mir jemand helfen könnte.

 

[mihe7]

Zunächst einmal kannst Du char wie int behandeln (ein char ist eine vorzeichenlose 16-bit Ganzzahl), lediglich bei der Ein- und Ausgabe musst Du etwas aufpassen.

Was die Eingabe der Untermengen betrifft: Du möchtest eine Menge von Mengen. Also musst Du auch ein entsprechendes Set verwenden (z. B. Set<Integer> subsets) und ein eingegebenes Subset dort hinzufügen.

Was den Vergleich betrifft: Du könntest eine Kopie der Obermenge anlegen, aus dieser alle Elemente, die in den betreffenden Subsets enthalten sind enternen und abschließend schauen, ob die Kopie der Obermenge leer ist. Umgekehrt kannst Du auch ein neues Set erstellen, das alle betreffenden Subsets zusammenfasst und abschließend per equals mit der Obermenge verglichen wird. Darüber hinaus gibt es auch die containsAll()-Methode, mit der Du prüfen kannst, ob eine Menge alle Elemente einer anderen Menge enthält.