Alle Möglichkeiten der Partitionierung eine Liste in zwei nicht-leeren Listen

Question

[0.0, 1.0, 2.0, 3.0, 4.0]

Ich habe 5 Zahlen und zwei Gruppen, links und rechts. Jede Nummer hat zwei Möglichkeiten - sie kann nach links oder rechts gehen. Ich brauche eine Liste, die alle Partitionierung der Liste [0,1,2,3,4] in zwei nicht leere Teile enthält. Zum Beispiel: [([0], [1,2,3,4]), ([0,1], [2,3,4]), ...,]

Beachten Sie, dass es a insgesamt (2^5 -2)/2 Partitionierung - Reihenfolge spielt keine Rolle und ich möchte keine Wiederholungen. Bedeutung I so etwas wie dieses nicht wollen tun (wenn meine Liste war [1,2,3,4]):

[] [1, 2, 3, 4] 
[1] [2, 3, 4] 
[2] [1, 3, 4] 
[1, 2] [3, 4] 
[3] [1, 2, 4] 
[1, 3] [2, 4] 
[2, 3] [1, 4] 
[1, 2, 3] [4] 
[4] [1, 2, 3] 
[1, 4] [2, 3] 
[2, 4] [1, 3] 
[1, 2, 4] [3] 
[3, 4] [1, 2] 
[1, 3, 4] [2] 
[2, 3, 4] [1] 
[1, 2, 3, 4] [] 

ich in all den itertools Funktionen und keine geschaut haben scheinen zu arbeiten.

---

Edit: für Liste [i für i in range (16)], die 16 Elemente, Wenn ich den folgenden Code, das ist, was ich sehe:

n = len(l)//2 + 1 
>>> xs = list(chain(*[combinations(l, i) for i in range(1, n)])) 
>>> pairs = [(list(x), list(set(l) - set(x))) for x in xs] 
>>> print len(pairs) 
    39202 
>>> (2**16-2)/2 
    32767 

In der Tat, Es funktioniert auch nicht für eine Liste mit 6 Elementen. Ich sehe nicht warum ...

Das Problem tritt bei allen geraden Längenlisten auf. Zum Beispiel, wenn ich eine Länge 2 Liste versuchen, erhalte ich:

[([0,0], [1,0]), ([1,0], [0,0])]

Answer 1

Das Zeug ist es in itertools, vielleicht hast du einfach nicht an den richtigen Stellen gesucht.

ist hier teh codez:

from collections import OrderedDict 
from itertools import chain, combinations 

def partition(L): 
    n = len(L)//2 + 1 
    xs = chain(*[combinations(L, i) for i in range(1, n)]) 
    pairs = (tuple(sorted([x, tuple(set(L) - set(x))])) for x in xs) 
    return OrderedDict.fromkeys(pairs).keys() 

Ausgang:

>>> for pair in partition([1,2,3,4]): 
...  left, right = map(list, sorted(pair, key=len)) 
...  print left, right 
... 
[1] [2, 3, 4] 
[2] [1, 3, 4] 
[3] [1, 2, 4] 
[4] [1, 2, 3] 
[1, 2] [3, 4] 
[1, 3] [2, 4] 
[1, 4] [2, 3]