Comment générer toutes les permutations d'une liste en Python ?

Question

Comment générer toutes les permutations d'une liste en Python, indépendamment du type d'éléments de cette liste.

Par exemple :

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]

EDIT : Eliben a indiqué une solution similaire à la mienne, bien que plus simple, donc je la choisis comme réponse acceptée, bien qu'apparemment Python 2.6 (qui n'a pas encore été publié) aura une solution intégrée dans le fichier de configuration de Python. itertools module :

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

Answer 1

Démarrer avec Python 2.6 (et si vous êtes sur Python 3) vous avez une standard-library outil pour cela : itertools.permutations .

---

Si vous utilisez un Python plus ancien (<2.6) pour une raison quelconque ou si vous êtes simplement curieux de savoir comment cela fonctionne, voici une bonne approche, tirée de http://code.activestate.com/recipes/252178/ :

def all_perms(elements):
    if len(elements) <=1:
        yield elements
    else:
        for perm in all_perms(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:]

Quelques approches alternatives sont répertoriées dans la documentation du site Web de la Commission européenne. itertools.permutations . En voici un :

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

Et un autre, basé sur 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

Et dans python 2.6 :

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

(retourné en tant que générateur. Utilisez list(permutations(l)) pour le retourner sous forme de liste).

Answer 3

Le code suivant n'est utilisé qu'avec Python 2.6 et supérieur

D'abord, importer itertools :

import itertools

Permutation (l'ordre importe) :

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)]

Combinaison (l'ordre n'a PAS d'importance) :

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

Produit cartésien (avec plusieurs itérables) :

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)]

Produit cartésien (avec un itérable et lui-même) :

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[0:i] + head[i+1:], tail+head[i])

appelé comme :

permutations('abc')

Answer 5

Cette solution met en œuvre un générateur, pour éviter de conserver toutes les permutations en mémoire :

def permutations (orig_list):
    if not isinstance(orig_list, list):
        orig_list = list(orig_list)

    yield orig_list

    if len(orig_list) == 1:
        return

    for n in sorted(orig_list):
        new_list = orig_list[:]
        pos = new_list.index(n)
        del(new_list[pos])
        new_list.insert(0, n)
        for resto in permutations(new_list[1:]):
            if new_list[:1] + resto <> orig_list:
                yield new_list[:1] + resto