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


Comment générer toutes les permutations d'une liste en Python, indépendamment du type d'éléments dans 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]

436
2017-09-19 18:41


origine


Réponses:


À partir de Python 2.6 (et si vous êtes sur Python 3) vous avez un bibliothèque standard outil pour cela: itertools.permutations.

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

Si vous utilisez un Python plus ancien (<2.6) pour une raison quelconque ou sont simplement curieux de savoir comment cela fonctionne, voici une belle 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 listées dans la documentation de itertools.permutations. 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)

314
2017-09-19 18:43



Et en Python 2.6 à partir de:

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

(renvoyé en tant que générateur. list(permutations(l)) retourner comme une liste.)


318
2017-09-19 18:48



Le code suivant avec Python 2.6 et supérieur UNIQUEMENT

D'abord, importer itertools:

import itertools

Permutation (l'ordre compte):

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

237
2017-10-04 12:18



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

33
2017-10-12 00:14



Cette solution implémente 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

19
2017-09-19 18:41



#!/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])

Sortie:

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

Comme je permute le contenu de la liste, un type de séquence mutable est requis en entrée. Par exemple. perm(list("ball")) va travailler et perm("ball") ne sera pas parce que vous ne pouvez pas changer une chaîne.

Cette implémentation Python est inspirée de l'algorithme présenté dans le livre Algorithmes informatiques de Horowitz, Sahni et Rajasekeran.


17
2017-08-14 23:58



Une manière tout à fait évidente à mon avis pourrait être aussi:

def permutList(l):
    if not l:
            return [[]]
    res = []
    for e in l:
            temp = l[:]
            temp.remove(e)
            res.extend([[e] + r for r in permutList(temp)])

    return res

13
2018-03-31 13:58