563 votes

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

Comment pouvez-vous générer toutes les permutations d'une liste en Python, indépendamment du type d'éléments de la 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 souligné une solution similaire à la mienne bien plus simple, je suis donc le choix de ce que l'on a Accepté la Réponse, bien qu'apparemment la version 2.6 de Python (qui n'a pas encore été dévoilé) aura un builtin solution dans le itertools module:

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

457voto

Eli Bendersky Points 82298

En commençant avec la version 2.6 de Python (et si vous êtes sur Python 3) vous avez un standard de la bibliothèque de l'outil pour cela: itertools.permutations.


Si vous utilisez un anciens Python (<2,6)que pour une raison ou sont simplement curieux de savoir comment cela fonctionne, voici une belle approche, prise 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:]

Un couple d'approches alternatives sont répertoriés dans la documentation de l' 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 de l'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)

331voto

Brian Points 48423

Et dans la version 2.6 de python:

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

(renvoyé comme un générateur. Utilisation de la liste(permutations(l)) pour y revenir une liste.)

268voto

e-satis Points 146299

Le code suivant avec Python 2.6 et supérieur UNIQUEMENT

Tout d'abord, importer itertools:

import itertools

Permutation (l'ordre est important):

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 iterables):

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

37voto

kx2k Points 131
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é aussi:

permutations('abc')

21voto

Ricardo Reyes Points 3428

Cette solution met en oeuvre un générateur, afin d'éviter la tenue de toutes les permutations sur la 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

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X