Suche Algorithmus (Kombinatorik)

[heiliga horsd]

Hallo,

ich bin auf der Suche nach einem Algorithmus und habe keine Ahnung wonach ich suchen soll. Im Endeffekt soll eine Menge an Zahlen in alle möglichen Teilmengen aufgeteilt werden, also wenn ich die Menge 1,2,3,4,5 habe möchte ich

{1},{2},{3},{4},{5}
{1,2},{3},{4},{5}
...
{1},{2,3,4,5}

haben. Kombinationen wie beispielsweise {1,3,5},{2},{4} sollen natürlich auch vorkommen.

Gibts da irgendwas in der Standardbibliothek was ich dafür verwenden könnte? Hat jemand ein Stichwort für mich?

Gruß,
heiliga horsd

[EyDu]

Hallo.

Mir fällt auch kein Name dazu ein, aber bist du sicher, dass du das machen möchtest? Die Komplexität sollte exponentiell sein, da dürftest du sehr schnell an Grenzen stoßen. Was hast du denn eigentlich vor? Vielleicht lässt sich das Problem etwas geschickter lösen.

[heiliga horsd]

Es geht darum, eine Menge an Zahlen in alle Untermengen zu zerlegen (Aufgabenstellung), und sowas geht IMO nunmal am besten mit dem Computer. Ich bin bereits auf Stirling-Zahlen gestoßen, aber die geben mir ja nur die Anzahl der Möglichkeiten und nicht die konkreten Kombinationen.

[EyDu]

Schon klar. Die Frage war eher: was hast du mit diesen Untermengen vor? Wenn es ein Optimierungs- oder Zerlegungsproblem ist, dann bestehen durchaus gute Chancen, dass es dafür eine Lösung gibt. Im Idealfall könntest du so die Zerlegung sparen und das eigentliche Problem behandeln.

[heiliga horsd]

Nope, nur die Mengen. Sinn dahinter ist mir zwar auch nicht ganz klar, aber die Aufgabenstellung reizt mich. Vielleicht werden die Mengen später für irgendetwas benötigt, davon wurde mir aber bisher noch nichts mitgeteilt.

[BlackJack]

@heiliga horsd: Müsste die letzte Zeile nicht {1,2,3,4,5} lauten?

Man könnte das vielleicht auf das Teilproblem runterbrechen alle Möglichkeiten die Menge auf n Teilmengen zu verteilen zu erzeugen. Das macht man dann für n=1 bis n = Anzahl der Elemente die es gibt.

[heiliga horsd]

Okay, aber wie mache ich das dann systematisch, damit ich auch wirklich alle erfasse?

[pillmuncher]

Code: Alles auswählen

def set_partitions(items):
    if not items:
        yield []
        return
    for i in xrange(2 ** len(items) / 2):
        parts = [[], []]
        for item in items:
            parts[i & 1].append(item)
            i >>= 1
        for each in set_partitions(parts[1]):
            yield [parts[0]] + each


for each in set_partitions([1, 2, 3, 4, 5]):
    print each

Das habe ich von hier: http://ideone.com/6dwp8. Ich habe es allerdings etwas angepasst.
Statt des & muss da & stehen. Leider ist die Code-Darstellung kaputt.

Die Anzahl der möglichen Partitionierungen einer Menge mit n Elementen ist die n-te Bell-Zahl (wir fangen bei 0 zu zählen an). Für 5 ist sie 52 für, für 5*5 bereits 4638590332229999353.

[EyDu]

Ich hoffe mal, dass ich keinen Denkfehler gemacht habe:

Code: Alles auswählen

import itertools
import operator

numbers = [1, 2, 3, 4]

def combine(n, prev=-1, num=(), depth=0):
    if n == depth:
        yield num
        return
    
    for i in xrange(prev+2):
        for value in combine(n, i, num+(i,), depth+1):
            yield value

n = len(numbers)
for mask in combine(n):
    groups = itertools.groupby(
                sorted(zip(mask, numbers)),
                key=operator.itemgetter(0))
    
    print [frozenset(map(operator.itemgetter(1), es)) for _, es in groups]

Viel schneller (von der Komplexität) dürfte es nicht gehen, da der Ansatz konstruktiv ist. (Das Erstellen der Tupel mittels + ist natürlich noch unglücklich, das könnte man mit Listen besser machen). Vielleicht ganz kurz die Idee dahinter:

Es wird eine Maske erzeugt, mit welcher die Werte in Gruppen gepackt werden. Eine Maske der Form (3,2,0,2) sagt, das erste Element kommt in Menge 4, das zweite Element in Menge 3, das dritte Element in Menge 1 und das vierte Element in Menge 3. Theoretisch müsste man jetzt alle Masken von (0, 0, 0, 0) bis (3, 3, 3, 3) durchprobieren. Jetzt ist offensichtlich, dass (3,2,0,2) äquivalent mit (0, 1, 2, 1) ist. Die Menge kann also verworfen werden. Offensichtlich muss man die Masken also normalisieren, um sie sinnvoll vergleichen zu können.

Die Normierung ist jetzt relativ einfach: Minimiere den Wert des Tupels, so dass die Struktur erhalten bleibt. Man fängt also mit den linken Element an (Wert a) und ersetzt dieses mit dem Wert 0. Alle Elemente die Vorher 0 waren werden nun durch a ersetzt:

(3,2,0,2) => (0,2,3,2)

Jetzt macht man mit dem zweiten Element (b) weiter und setzt dieses auf eins (falls es nicht bereits < 1) ist. Alle Einsen werden ggf. wieder durch b ersetz.

(0, 2, 3, 2) => (0, 1, 3, 1)

Weiter mit dem dritten Element (c), welches durch 2 ersetzt wird. Ggf. werden auch hier alle Zweien durch c ersetzt.

(0, 1, 3, 1) => (0, 1, 2, 1)

Offensichtlich sind nun keine weiteren Umformungen mehr möglich, damit ist das Tupel minimal.

Das ganze kann man nun durch einen kleien Trick konstruktiv machen: Das Element i+1 darf um höchstens 1 größer sein als das Element i (von links gezählt). Damit ergibt sich das obige xrange(prev+2).

Edit: Da ist offensichtlich noch ein Problem bei set([2], [4], [1,3]), ich schaue nachher noch einmal drüber.

Edit 2: So, nun aber:

Code: Alles auswählen

import itertools
import operator

numbers = [1, 2, 3, 4]

def combine(n, m=-1, num=(), depth=0):
    if n == depth:
        yield num
        return
    
    for i in xrange(m+2):
        for value in combine(n, m+1 if i>m else m, num+(i,), depth+1):
            yield value

n = len(numbers)
for mask in combine(n):
    groups = itertools.groupby(
                sorted(zip(mask, numbers)),
                key=operator.itemgetter(0))
    
    print [frozenset(map(operator.itemgetter(1), es)) for _, es in groups]

Natürlich darf das i+1-te Element nicht nur um 1 größer sein als das i-te, sondern um 1 größer als alle vorangegangenen Elemente.

[heiliga horsd]

Ich habe jetzt mal als erstes die Lösung von pillmuncher ausprobiert und die funktioniert einwandfrei! Danke an alle!

Gruß HH