Wie kann man alle Permutationen einer Liste erzeugen?

Question

Wie erzeugt man in Python alle Permutationen einer Liste, unabhängig vom Typ der Elemente in dieser Liste?

Zum Beispiel:

permutations([])
[]

permutations([1])
[1]

permutations([1, 2])
[1, 2]
[2, 1]

permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Answer 1

Utilisez itertools.permutations de la Standardbibliothek :

import itertools
list(itertools.permutations([1, 2, 3]))

---

Angepasst von ici ist eine Demonstration, wie itertools.permutations umgesetzt werden könnten:

def permutations(elements):
    if len(elements) <= 1:
        yield elements
        return
    for perm in permutations(elements[1:]):
        for i in range(len(elements)):
            # nb elements[0:1] works in both string and list contexts
            yield perm[:i] + elements[0:1] + perm[i:]

Eine Reihe von alternativen Ansätzen sind in der Dokumentation von itertools.permutations . Hier ist eine:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

Und eine weitere, die auf itertools.product :

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

Answer 2

Para Python 2.6 weiter:

import itertools
itertools.permutations([1, 2, 3])

Dieser kehrt als Generator zurück. Verwenden Sie list(permutations(xs)) als Liste zurückzugeben.

Answer 3

Erstens: Einfuhr itertools :

import itertools

Permutation (die Reihenfolge ist wichtig):

print(list(itertools.permutations([1,2,3,4], 2)))
[(1, 2), (1, 3), (1, 4),
(2, 1), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 4),
(4, 1), (4, 2), (4, 3)]

Kombination (die Reihenfolge spielt KEINE Rolle):

print(list(itertools.combinations('123', 2)))
[('1', '2'), ('1', '3'), ('2', '3')]

Kartesisches Produkt (mit mehreren Iterablen):

print(list(itertools.product([1,2,3], [4,5,6])))
[(1, 4), (1, 5), (1, 6),
(2, 4), (2, 5), (2, 6),
(3, 4), (3, 5), (3, 6)]

Kartesisches Produkt (mit einem Iterablen und sich selbst):

print(list(itertools.product([1,2], repeat=3)))
[(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]

Answer 4

def permutations(head, tail=''):
    if len(head) == 0:
        print(tail)
    else:
        for i in range(len(head)):
            permutations(head[:i] + head[i+1:], tail + head[i])

genannt als:

permutations('abc')

Answer 5

#!/usr/bin/env python

def perm(a, k=0):
   if k == len(a):
      print a
   else:
      for i in xrange(k, len(a)):
         a[k], a[i] = a[i] ,a[k]
         perm(a, k+1)
         a[k], a[i] = a[i], a[k]

perm([1,2,3])

Ausgabe:

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

Da ich den Inhalt der Liste austausche, ist ein veränderbarer Sequenztyp als Eingabe erforderlich. Z.B.. perm(list("ball")) wird funktionieren und perm("ball") nicht, weil man eine Zeichenkette nicht ändern kann.

Diese Python-Implementierung ist von dem Algorithmus inspiriert, der in dem Buch Computer-Algorithmen von Horowitz, Sahni und Rajasekeran .