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.