Strings untereinander in einer Liste vergleichen

Bitte aktiviere JavaScript!
Hallo in die Runde,

ich weiß nicht ob der Titel schon aussagekräftig genug ist, aber ich habe folgendes vor:
Gegeben ist ein String Array oder eine ArrayListe (bei meiner jetzigen Implementierung nutze ich die Liste) und in dieser Liste bzw in dem String Array sind verschiedene Strings gespeichert. Das könnte nun etwa folgendermaßen aussehen:
{"A", "B", "AB", "C", "AC", "ABC"}
Ich hoffe ich kann das sprachlich richtig rüberbringen (mathematisch wäre das eher weniger das Problem, nur sprachlich ist das was ich jetzt sagen möchte vielleicht nicht so exakt). Ich möchte nun die Obermenge dieses String Arrays bzw. dieser Liste ermitteln. Jetzt könnte man ja auf die Idee kommen mit dem Contains Befehl zu Arbeiten für folgendes Beispiel würde das auch funktionieren: "A", "B", "AB", "BC", "ABC". ABC ist dann die gemeinsame Obermenge. Jetzt hatte ich das Beispiel vom Anfang extra so komisch gestellt, denn der Contains Befehl würde im ersten Fallbeispiel "A", "B", "AB", "C", "AC", "ABC", nicht korrekt arbeiten. Siehe hierzu AC und ABC, in der Mengennotation ausgedrückt {A,C}, {A,B,C}, hier erkennt man eigentlich sofort, dass ABC die Obermenge ist. Der Computer erkennt das leider nicht so gut, zumindest mit dem Contains Befehl nicht :)

Was ich nun gerne machen Möchte, ist mir die Obermenge von verschiedenen Eingaben ausgeben zu lassen, OHNE dabei komplexere Programmier-Konstrukte zu verwenden. Ich möchte das Ganze so simpel wie möglich halten. Darum verwende ich auch nur die aller notwendigsten Methoden. Ich habe hier auch schon eine erste Version auf die Beine gestellt, die mir allem Anschein nach zuurteilen auch die richtige Ausgabe liefert. Für die Array Liste habe ich mich entschieden, weil ich mir das an dieser Stelle etwas einfacher machen wollte. Ich würde das aber auch gerne mal mit einem fixen String Array versuchen, wobei ich dann mit Remove ein Problem bekomme.

Ich bin nun gewissermaßen auf der Suche nach einer Code Optimierung meines aktuellen Codes. Wichtig ist mir dabei, dass alles einfach bleibt. Was ich auf jedenfall vermeiden möchte ist, dass nun irgendeine Bibliothek vorgeschlagen wird. Ich möchte also wirklich mit den Java Basics arbeiten und dabei immer noch etwas performantes erzeugen. Ich bin also durchaus an einer Optimierung und einer entsprechenden Implementierung unter Verwendung eines String Arrays oder einer Liste interessiert (Die Listenimplementierung (siehe aktuellen Code), habe ich verwendet, da ich hier den netten remove Befehl verwenden konnte. Mit einem String Array ist das vllt. schwerer (aber es interessiert mich)).

Hier einmal meine ersten Gehversuche:

Java:
import java.util.ArrayList;

public class TestKlasse {

    public static void main(String[] args) {
        String[] str1 = {"D","B","BC","CB","C","AB","AC","ABC"};

       
        ArrayList<String> ls = new ArrayList<String>();
        for(int i = 0; i < str1.length; i++) {
            ls.add(str1[i]);
        }
       
        Tester(ls);
       
        for(int i=0; i<ls.size(); i++) {
            System.out.println(ls.get(i));
        }
       

    }

    public static void Tester(ArrayList<String> ls) {
        int vglAnzahl = 0;
        for(int i = 0; i < ls.size(); i++) {
            for(int j = 0; j < ls.size(); j++) {
                if(i != j) {
                    for(int k = 0; k < ls.get(i).length(); k++) {
                        for(int l = 0; l < ls.get(j).length(); l++) {
                            if(ls.get(i).charAt(k) == ls.get(j).charAt(l)) {
                                System.out.println("Char gleich...");
                                vglAnzahl++;
                                if(vglAnzahl == ls.get(j).length()) {
                                    System.out.println("Empfehlung : " + ls.get(j) + " löschen");
                                    ls.remove(j);
                                    vglAnzahl = 0;
                                    l = 0;
                                    k = 0;
                                    i = 0;
                                    j = 0;
                                }
                            }
                        }
                       
                    }
                }
                vglAnzahl = 0;
            }
        }
    }
}

Ich würde mich sehr über eure Meinungen und Ansätze/Verbesserungen/Optimierungen freuen und freue mich jetzt erstmal auf mögliche Antworten. Ich hoffe auch, es ist einigermaßen verständlich was ich überhaupt vorhabe, falls nicht, kann ich das auch gerne noch etwas präzisieren. Ich bedanke mich erstmal bis hierhin!
 
Zuletzt bearbeitet:
Vielleicht doch eher mathematisch: Du hast Mengen M1, ..., Mn und Du möchtest jetzt wissen, ob und wenn ja welches i (1<=i<=n) die Vereinigung aller Mengen ist?
 
Ja das Könnte es schon treffen :)

Vielleicht mit Bezug zum Beispiel:
{{D},{B},{BC},{CB},{C},{AB},{AC},{ABC}}, hierbei müsste ich dann folgende Ausgabe erwarten {D},{ABC}
 
Die Menge {A,B,C,D} ist die Obermenge, das würde ich erwarten. Vielleicht sollte ich erwähnen, dass ich ABCD als einzelne Elemente in der Menge sehe also {A,B,C,D}
 
Also ich versuche zu jeder Menge die in der Grundmenge enthalten ist eine Obermenge zu finden, gibt es keine Obermenge, dann gebe ich eine Teillösung aus:

Sagen wir ich habe verschiedene Mengen in X, so in etwa X={{D}, {A,B}, {A,B,C}} die Obermenge von {D} und {A,B} existiert nicht, daher belasse ich {D} und {A,B} in der Menge X. Jetzt teste ich, ob es eine Obermenge von {A,B}, {A,B,C} gibt. Ja die gibt es das ist folgende: {A,B,C}, weil es diese Obermenge zwischen {A,B} und {A,B,C} gibt, resultiert hier {A,B,C}, sodass nun in X steht: X={{D}, {A,B,C}}
 
Kommt jetzt drauf an, wie du genau "Obermenge" definierst. Die Obermenge von {A, B} und {C, D} kann genausogut auch {A, B, C, D} sein. Was du meinst, würde ich nicht als "Obermenge" bezeichnen. Bei dir ist eine Menge eine "Obermenge", wenn die Schnittmenge der Mengen, deren Obermenge sie ist, nicht leer ist.
 
Java:
import static java.util.stream.Collectors.toSet;
import static java.util.stream.Stream.of;
import java.util.ArrayList;
import java.util.Set;
import java.util.stream.Stream;
public class Mengen {
  public static Stream<Set<Character>> obermengen(Stream<String> mengen) {
    return mengen.collect(ArrayList<Set<Character>>::new, (r, s) -> {
      Set<Character> sc = s.chars().mapToObj(e -> (char) e).collect(toSet());
      r.stream()
       .filter(e -> e.stream().anyMatch(sc::contains))
       .findFirst()
       .map(set -> set.addAll(sc))
       .orElseGet(() -> r.add(sc));
    }, ArrayList::addAll).stream();
  }
  public static void main(String[] args) {
    obermengen(of("A", "AB", "BC", "D")).forEach(System.out::println);
    // [A, B, C]
    // [D]
  }
}
 
Okay, dann nochmal ganz formal:
Die Obermenge `O` ist die Vereinigungsmenge jener Mengen `Ms`, so dass für je zwei Mengen `M1` und `M2` in `Ms` gilt: `M1` ist Obermenge von `M2` oder `M2` ist Obermenge von `M1`.
Das käme dann für {A}, {AB}, {BC}, {D} => {AB}, {BC, {D} hin, da weder {A} Obermenge von {BC} ist, noch ist {BC} Obermenge von {A}.

Code nach dieser Definition:
Java:
import static java.util.stream.Collectors.toSet;
import static java.util.stream.Stream.of;
import java.util.ArrayList;
import java.util.Set;
import java.util.stream.Stream;
public class Mengen {
  private static Stream<Set<Character>> obermengen(Stream<String> mengen) {
    return mengen.collect(ArrayList<Set<Character>>::new, (r, s) -> {
      Set<Character> sc = s.chars().mapToObj(e -> (char) e).collect(toSet());
      r.stream()
       .filter(e -> sc.containsAll(e) || e.containsAll(sc))
       .findFirst()
       .map(set -> set.addAll(sc))
       .orElseGet(() -> r.add(sc));
    }, ArrayList::addAll).stream();
  }
  public static void main(String[] args) {
    obermengen(of("A", "AB", "BC", "D")).forEach(System.out::println);
    // [A, B]
    // [B, C]
    // [D]
  }
}
 
Zuletzt bearbeitet:
A und B seien Mengen. Ist B eine Teilmenge von A, so ist A eine Obermenge von B. Ich versuche wenn man das so sagen kann gemeinsame Obermengen zu finden. Darum wird X={{D}, {A,B}, {A,B,C}} bei mir zu X={{D}, {A,B,C}} vereinfacht, da die Menge {A,B,C} die Obermenge von {A,B} ist. {D} ist hingegen weder in {A,B} noch in {A,B,C} enthalten, sodass es hier keine (gemeinsame) Obermenge gibt.

Dein Code liefert die richtige Ausgabe! Das würde passen, zumindest nach meiner Auffassung. Nur ich würde gerne recht simpel bleiben wollen, daher habe ich in meinem Code bewusst auf sowas hier:
import static java.util.stream.Collectors.toSet;
import static java.util.stream.Stream.of;
verzichtet. Ich wollte das mit möglichst einfachen Mitteln umsetzen, wobei sich einfach auf Java Basics bezieht. Ich vergeb den Kommentaren hier als Belohnung erstmal ein "Like" für eure Mühe und hoffe natürlich auf weitere Beiträge :)

Aber ist denn meine Idee soweit erstmal verständlich(er) geworden? Auf ein paar (Code)-Anregungen wäre ich sehr gespannt :)
 
Zuletzt bearbeitet:
Ich wollte das mit möglichst einfachen Mitteln umsetzen, wobei sich einfach auf Java Basics bezieht
Java:
public class start {
    public static void main(String[] args) {
        String sets[] = { "A", "AB", "BC", "D" };
        ArrayList<String> superSets = getSuperSets(sets);
        for (String s : superSets)
            System.out.println("[" + s + "]");
    }

    public static ArrayList<String> getSuperSets(String[] sets) {
        ArrayList<String> supersets = new ArrayList<String>();
        for (String s : sets) // all sets at start
            supersets.add(s);
        for (int i = 0; i < sets.length; i++) {
            for (int testId = 0; testId < sets.length; testId++) {
                if (isSubSet(sets[testId], sets[i])) {
                    supersets.remove(sets[testId]); // remove subset
                    continue;
                }
            }
        }
        return supersets;
    }

    private static boolean isSubSet(String subSet, String superSet) {
        if (superSet.length() <= subSet.length())
            return false;
        for (int i = 0; i < subSet.length(); i++) {
            if (!superSet.contains(subSet.charAt(i) + ""))
                return false;
        }
        return true;
    }
}
 
Java:
public class Mengen {
    private static List<String> obermengen(List<String> mengen) {
        Set<Set<Character>> sets = new HashSet<>();
        for (String s : mengen) {
            Set<Character> menge = zeichen(s);
            boolean neuesElement = true;
            for (Set<Character> set : sets) {
                if (set.containsAll(menge) || menge.containsAll(set)) {
                    set.addAll(menge);
                    neuesElement = false;
                }
            }
            if (neuesElement) {
                sets.add(menge);
            }
        }

        return stringList(sets);
    }

    private static Set<Character> zeichen(String s) {
        Set<Character> result = new HashSet<>();
        for (char ch : s.toCharArray()) {
            result.add(ch);
        }
        return result;
    }

    private static List<String> stringList(Set<Set<Character>> sets) {
        List<String> result = new ArrayList<>();
        for (Set<Character> set : sets) {
            result.add(set.toString());
        }
        return result;
    }

    public static void main(String[] args) {
        obermengen(Arrays.asList("A", "AB", "BC", "D")).forEach(System.out::println);
    }
}
 
Guten Morgen,

ich habe beide Programme nochmal mit einem neuen Test Array getestet "D","B","BC","ABC","CB","C","AB","AC","AC","D"

@Blender3D dein Programm gibt hierbei folgendes aus:
[D]
[ABC]
[D]
Es sollten aber "nur" [D] und [ABC] sein, das eine [D] ist zu viel ;-) (Mir gefällt aber die Struktur deines Programms!, wenn du Lust hast könntest du ja noch eine Verbesserung vornehmen, sodass die Ausgabe dann passt)

@mihe7 dein Programm gibt hierbei folgendes aus:
[A, B, C]
[D]
Das ist absolut richtig!

Mein Programm gibt ebenfalls:
[ABC]
[D]
 
Es sollten aber "nur" [D] und [ABC] sein, das eine [D] ist zu viel ;-) (Mir gefällt aber die Struktur deines Programms!, wenn du Lust hast könntest du ja noch eine Verbesserung vornehmen, sodass die Ausgabe dann passt)
Das hängt davon ab, da ich davon ausging, dass das arrray set keine doppelten Einträge enthält.
Das lässt sich aber sehr einfach beheben, indem du doppelte Eintrage vermeidest. Wenn man bei ArrayList bleibt durch eine Bedingung. Besser wäre statt Arraylist gleich Set zu benutzen.
Java:
public class start {
    public static void main(String[] args) {
        String sets[] = {  "D","B","BC","ABC","CB","C","AB","AC","AC","D"};
        ArrayList<String> superSets = getSuperSets(sets);
        for (String s : superSets)
            System.out.println("[" + s + "]");
    }
    public static ArrayList<String> getSuperSets(String[] sets) {
        ArrayList<String> supersets = new ArrayList<String>();
        for (String s : sets) { // all unique sets at start
            if (!supersets.contains(s))
                supersets.add(s);
        }
        for (int i = 0; i < sets.length; i++) {
            for (int testId = 0; testId < sets.length; testId++) {
                if (isSubSet(sets[testId], sets[i])) {
                    supersets.remove(sets[testId]); // remove subset
                    continue;
                }
            }
        }
        return supersets;
    }
    private static boolean isSubSet(String subSet, String superSet) {
        if (superSet.length() <= subSet.length())
            return false;
        for (int i = 0; i < subSet.length(); i++) {
            if (!superSet.contains(subSet.charAt(i) + ""))
                return false;
        }
        return true;
    }
}
 
Besser wäre statt Arraylist gleich Set zu benutzen.
Hier die Variante mit einem Set
Java:
public class start {
    public static void main(String[] args) {
        String sets[] = { "D", "B", "BC", "ABC", "CB", "C", "AB", "AC", "AC", "D" };
        Set<String> superSets = getSuperSets(sets);
        for (String s : superSets)
            System.out.println("[" + s + "]");
    }

    public static Set<String> getSuperSets(String[] sets) {
        Set<String> supersets = new HashSet<String>(Arrays.asList(sets));
        for (String s : sets) // all sets unique at start
            supersets.add(s);
        for (int i = 0; i < sets.length; i++) {
            for (int testId = 0; testId < sets.length; testId++) {
                if (isSubSet(sets[testId], sets[i])) {
                    supersets.remove(sets[testId]); // remove subset
                    continue;
                }
            }
        }
        return supersets;
    }

    private static boolean isSubSet(String subSet, String superSet) {
        if (superSet.length() <= subSet.length())
            return false;
        for (int i = 0; i < subSet.length(); i++) {
            if (!superSet.contains(subSet.charAt(i) + ""))
                return false;
        }
        return true;
    }
}
 
Passende Stellenanzeigen aus deiner Region:

Oben