Unterschiedliche Untermengen generieren

[Fridge]

Hallo,

ich suche nach einem Algorithmus, der mir aus einer Menge L von Zahlen alle unterschiedlichen Untermengen der Länge k generiert.

Für den Namen eines solchen Algorithmus wäre ich sehr dankbar, bzw. einen Link oder derartiges, der die genaue Funktionsweise erklärt (ev. mit Implementierung in höherer Programmiersprache, vorzugsweise Java).

Habe mich bereits im Netz umgeschaut, bin aber nur auf die Algorithmen gestoßen, die alle Permutationen generieren. Ich habe keine Algorithmen gefunden, die alle unterschiedlichen Mengen mit k Elementen generieren. Letztendlich läuft das Ganze ja auf den Binomialkoeffizienten heraus.

Die Aufgabe ist also: Generiere aus dem Array a der Länge 5 alle unterschiedlichen Untermengen mit 2 Elementen.

Dann müssten ja insgesamt 5 über 2 = 10 Möglichkeiten herauskommen.

LG

[flashpixx]

Wenn Du alle Mengen brauchst, ist das eh NP-vollständig und wird bei entsprechend großen Mengen nicht mehr effizient funktionieren. Man müsste über den Bahn-Stabilisator-Algorithmus die entsprechenden Permutationen bei großen Mengen konstruieren können. Letztendlich bleibt das Problem aber NP-vollständig.

Wenn Du alle Mengen brauchst, dann musst Du sie eben iterativ konstruieren.

[Fridge]

Wenn Du alle Mengen brauchst, dann musst Du sie eben iterativ konstruieren.

Wie schaffe ich das aber? Die naive Methode wäre ja, wenn man beispielsweise alle 3 elementigen Untermengen haben möchte, 3 for-Schleifen zu machen. Dann würde man die entsprechenden Kombinationen herausbekommen. Aber wie programmiere ich ein solches Verfahren so, dass es auch funktioniert, wenn ich 2er Paare haben will oder 4-er Tupel?

Tut mir Leid, habe leider nicht viel Ahnung von so etwas.

PS: Wie heißt der Algorithmus eigentlich auf Englisch, weil so auf die Schnelle finde ich keine Implementierungen oder ähnliches

Bearbeitet 5. September 2011 von Fridge

[flashpixx]

Die naive Methode wäre ja, wenn man beispielsweise alle 3 elementigen Untermengen haben möchte, 3 for-Schleifen zu machen.

Nein, muss man nicht, sondern man konstruiert die Mengen rekursiv.

PS: Wie heißt der Algorithmus eigentlich auf Englisch, weil so auf die Schnelle finde ich keine Implementierungen oder ähnliches

Gruppenoperation

GAP Manual: 8.16 Orbits

GAP Manual: 8.22 Stabilizer

Eine fertige Implementierung ist mir nicht bekannt, denn es kommt gerade bei großen Mengen auch auf effiziente Datenstrukturen an

[Fridge]

Also zur Erklärung: So groß werden die Mengen nicht also wenn man das von Binomialkoeffizient her betrachtet, dann ist der obere Wert(max. vllt. so 10) nur minimal größer als der untere. Also am Ende hat man relativ wenige Untermengen. Das Problem ist, wie du ja sagst, dass die Menge die rauskommt nicht so viele Elemente hat, dass es aber sehr rechenintensiv ist, diese Untermengen zu erzeugen.