In Python, wie generiere ich alle Permutationen einer Zeichenfolge von 0 und 1 in der Reihenfolge?

Question

Ich versuche, eine Zeichenfolge von 0s und 1s einer beliebigen Länge zu permutieren. Ich habe eine Menge Antworten zu diesem Thema gesehen, die es so machen, dass das Ergebnis für eine Zeichenfolge der Länge n für n=3 wie folgt aussieht.

000 
001 
010 
011 
100 
101 
110 
111 

Aber das ist nicht was ich brauche!

Ich brauche es so für lang sein 3:

000 
100 
010 
001 
110 
101 
011 
111 

Für Länge 4 dies wäre:

0000 
1000 
0100 
0010 
0001 
1100 
1010 
1001 
0110 
0101 
0011 
1110 
1101 
1011 
0111 
1111 

Für Länge 5, es wäre:

00000 
10000 
01000 
00100 
00010 
00001 
11000 
10100 
10010 
10001 
01100 
01010 
01001 
00110 
00101 
00011 
11100 
11010 
11001 
10110 
10101 
10011 
01110 
01101 
01011 
00111 
11110 
11101 
11011 
10111 
01111 
11111 

etc ..

ich kann einfach nicht f Finde einen Algorithmus dafür, kann mir jemand helfen?

Edit: Ich habe was darauf hindeutet, Pop-up, dass ich die Antwort an anderer Stelle auf dieser Seite zu finden. Ich bin neu hier, also könnte ich nicht richtig verstehen, aber die einzige Überlappung, die ich in den zwei Fragen sah, war das Wort Permutation.

Answer 1

Dies funktioniert für mich. Es erzeugt jedoch nicht die Elemente in der richtigen Reihenfolge, sondern produziert sie zuerst und sortiert sie dann.

n = 5 
i = np.array(np.indices(n * (2,))).reshape(n, -1) 
i[:, np.argsort(i.sum(0)[::-1], kind='mergesort')].T[::-1] 

Es sortiert die binären Worte durch die Summe ihrer Ziffern, eine stabile Art verwendet wird, das heißt eine, die im Falle eines Unentschiedens die ursprüngliche Ordnung beibehalten.

Eine Lösung, die die Wörter in Reihenfolge erzeugt, kann dieses Schleifen über die Anzahl von Einsen mit itertools

itertools.chain((n*(0,),), (l[0] * (0,) + sum(((1,) + (i-j-1) * (0,) for i, j in zip(l[1:], l[:-1])),()) + (1,) + (n-l[-1]-1)*(0,) for k in range(1,n+1) for l in itertools.combinations(range(n), k))) 

konstruiert werden k (k = 0 und spezielle verrohrten vorangestellt itertools.chain verwenden). Für jede k verwendet es itertools.combinations alle k Element Subsets l des Satzes `{0, 1, ..., n -1} und übersetzt jede Untergruppe in ein binäres Wort zu schaffen. Diese Übersetzung funktioniert, indem ein eine für jedes Element von l setzen und die Berechnung, wie viele Nullen müssen gehen dazwischen. Führende und nachfolgende Nullen mussten speziell angepasst werden.

Beispielausgabe: numpy:

# array([[0, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], 
     [0, 0, 0, 1, 0], [0, 0, 0, 0, 1], [1, 1, 0, 0, 0], [1, 0, 1, 0, 0], 
     [1, 0, 0, 1, 0], [1, 0, 0, 0, 1], [0, 1, 1, 0, 0], [0, 1, 0, 1, 0], 
     [0, 1, 0, 0, 1], [0, 0, 1, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 1], 
     [1, 1, 1, 0, 0], [1, 1, 0, 1, 0], [1, 1, 0, 0, 1], [1, 0, 1, 1, 0], 
     [1, 0, 1, 0, 1], [1, 0, 0, 1, 1], [0, 1, 1, 1, 0], [0, 1, 1, 0, 1], 
     [0, 1, 0, 1, 1], [0, 0, 1, 1, 1], [1, 1, 1, 1, 0], [1, 1, 1, 0, 1], 
     [1, 1, 0, 1, 1], [1, 0, 1, 1, 1], [0, 1, 1, 1, 1], [1, 1, 1, 1, 1]]) 

itertools:

list(_) 
# [(0, 0, 0, 0, 0), (1, 0, 0, 0, 0), (0, 1, 0, 0, 0), (0, 0, 1, 0, 0), (0, 0, 0, 1, 0), (0, 0, 0, 0, 1), 
    (1, 1, 0, 0, 0), (1, 0, 1, 0, 0), (1, 0, 0, 1, 0), (1, 0, 0, 0, 1), (0, 1, 1, 0, 0), (0, 1, 0, 1, 0), 
    (0, 1, 0, 0, 1), (0, 0, 1, 1, 0), (0, 0, 1, 0, 1), (0, 0, 0, 1, 1), (1, 1, 1, 0, 0), (1, 1, 0, 1, 0), 
    (1, 1, 0, 0, 1), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (1, 0, 0, 1, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), 
    (0, 1, 0, 1, 1), (0, 0, 1, 1, 1), (1, 1, 1, 1, 0), (1, 1, 1, 0, 1), (1, 1, 0, 1, 1), (1, 0, 1, 1, 1), 
    (0, 1, 1, 1, 1), (1, 1, 1, 1, 1)]