Cómo generar todas las permutaciones de una lista en Python

¿Cómo genera todas las permutaciones de una lista en Python, independientemente del tipo de elementos en esa lista?

Por ejemplo:

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] 

Comenzando con Python 2.6 (y si estás en Python 3) tienes una herramienta de biblioteca estándar para esto: itertools.permutations .

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

Si está usando un Python antiguo (<2.6) por alguna razón o simplemente tiene curiosidad por saber cómo funciona, aquí hay un buen enfoque, tomado 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 par de enfoques alternativos se enumeran en la documentación de itertools.permutations . Aquí hay uno:

 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, nr, -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 

Y otro, basado en 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) 

Y en Python 2.6 en adelante:

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

(devuelto como un generador. Use la list(permutations(l)) para regresar como una lista.)

El siguiente código con Python 2.6 y superior SOLAMENTE

En primer lugar, importar itertools :

 import itertools 

Permutación (el orden importa):

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

Combinación (el orden NO importa):

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

Producto cartesiano (con varios 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)] 

Producto cartesiano (con una iterable y sí):

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

llamado:

 permutations('abc') 

Esta solución implementa un generador, para evitar mantener todas las permutaciones en la memoria:

 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 rest in permutations(new_list[1:]): if new_list[:1] + rest <> orig_list: yield new_list[:1] + resto 
 #!/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]) 

Salida:

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

Como estoy intercambiando el contenido de la lista, se requiere un tipo de secuencia mutable como entrada. Por ejemplo, perm(list("ball")) funcionará y perm("ball") no funcionará porque no puedes cambiar una cadena.

Esta implementación de Python está inspirada en el algoritmo presentado en el libro Algoritmos de computadora de Horowitz, Sahni y Rajasekeran .

El siguiente código es una permutación in situ de una lista determinada, implementada como un generador. Como solo devuelve referencias a la lista, la lista no debe modificarse fuera del generador. La solución es no recursiva, por lo que utiliza poca memoria. Trabaja bien también con múltiples copias de elementos en la lista de entrada.

 def permute_in_place(a): a.sort() yield list(a) if len(a) <= 1: return first = 0 last = len(a) while 1: i = last - 1 while 1: i = i - 1 if a[i] < a[i+1]: j = last - 1 while not (a[i] < a[j]): j = j - 1 a[i], a[j] = a[j], a[i] # swap the values r = a[i+1:last] r.reverse() a[i+1:last] = r yield list(a) break if i == first: a.reverse() return if __name__ == '__main__': for n in range(5): for a in permute_in_place(range(1, n+1)): print a print for a in permute_in_place([0, 0, 1, 1, 1]): print a print 

Una forma bastante obvia en mi opinión podría ser también:

 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 

En un estilo funcional

 def addperm(x,l): return [ l[0:i] + [x] + l[i:] for i in range(len(l)+1) ] def perm(l): if len(l) == 0: return [[]] return [x for y in perm(l[1:]) for x in addperm(l[0],y) ] print perm([ i for i in range(3)]) 

El resultado:

 [[0, 1, 2], [1, 0, 2], [1, 2, 0], [0, 2, 1], [2, 0, 1], [2, 1, 0]] 
 list2Perm = [1, 2.0, 'three'] listPerm = [[a, b, c] for a in list2Perm for b in list2Perm for c in list2Perm if ( a != b and b != c and a != c ) ] print listPerm 

Salida:

 [ [1, 2.0, 'three'], [1, 'three', 2.0], [2.0, 1, 'three'], [2.0, 'three', 1], ['three', 1, 2.0], ['three', 2.0, 1] ] 

Utilicé un algoritmo basado en el sistema de números factoriales : para una lista de longitud n, puede ensamblar cada elemento de permutación por elemento, seleccionando entre los elementos que quedan en cada etapa. Tiene n opciones para el primer elemento, n-1 para el segundo y solo una para el último, por lo que puede usar los dígitos de un número en el sistema de números factoriales como los índices. De esta manera, los números 0 a n! -1 corresponden a todas las posibles permutaciones en orden lexicográfico.

 from math import factorial def permutations(l): permutations=[] length=len(l) for x in xrange(factorial(length)): available=list(l) newPermutation=[] for radix in xrange(length, 0, -1): placeValue=factorial(radix-1) index=x/placeValue newPermutation.append(available.pop(index)) x-=index*placeValue permutations.append(newPermutation) return permutations permutations(range(3)) 

salida:

 [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]] 

Este método no es recursivo, pero es un poco más lento en mi computadora y xrange genera un error cuando n. es demasiado grande para convertirlo en un entero largo C (n = 13 para mí). Fue suficiente cuando lo necesité, pero no es itertools.permutations por un tiro largo.

Tenga en cuenta que este algoritmo tiene una complejidad de tiempo n factorial , donde n es la longitud de la lista de entrada

Imprimir los resultados en la ejecución:

 global result result = [] def permutation(li): if li == [] or li == None: return if len(li) == 1: result.append(li[0]) print result result.pop() return for i in range(0,len(li)): result.append(li[i]) permutation(li[:i] + li[i+1:]) result.pop() 

Ejemplo:

 permutation([1,2,3]) 

Salida:

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

De hecho, se puede iterar sobre el primer elemento de cada permutación, como en la respuesta de tzwenn; Prefiero escribir esta solución de esta manera:

 def all_perms(elements): if len(elements) <= 1: yield elements # Only permutation possible = no permutation else: # Iteration over the first element in the result permutation: for (index, first_elmt) in enumerate(elements): other_elmts = elements[:index]+elements[index+1:] for permutation in all_perms(other_elmts): yield [first_elmt] + permutation 

Esta solución es un 30% más rápida, aparentemente gracias a la recursión que termina en len(elements) <= 1 lugar de 0 . También es mucho más eficiente en memoria, ya que utiliza una función de generador (a través del yield ), como en la solución de Riccardo Reyes.

Esto está inspirado en la implementación de Haskell utilizando la comprensión de lista:

 def permutation(list): if len(list) == 0: return [[]] else: return [[x] + ys for x in list for ys in permutation(delete(list, x))] def delete(list, item): lc = list[:] lc.remove(item) return lc 

Para el rendimiento, una solución numpy inspirada en Knuth , (p22):

 from numpy import empty, uint8 from math import factorial def perms(n): f = 1 p = empty((2*n-1, factorial(n)), uint8) for i in range(n): p[i, :f] = i p[i+1:2*i+1, :f] = p[:i, :f] # constitution de blocs for j in range(i): p[:i+1, f*(j+1):f*(j+2)] = p[j+1:j+i+2, :f] # copie de blocs f = f*(i+1) return p[:n, :] 

Copiar grandes bloques de memoria ahorra tiempo: es 20 veces más rápido que la list(itertools.permutations(range(n)) :

 In [1]: %timeit -n10 list(permutations(range(10))) 10 loops, best of 3: 815 ms per loop In [2]: %timeit -n100 perms(10) 100 loops, best of 3: 40 ms per loop 

Perdone mi analfabetismo de python ya que no ofreceré la solución en python. Como no sé qué método utiliza python 2.6 para generar las permutaciones y el uno de eliben se parece a la generación de permutaciones de Johnson-Trotter, puede buscar un artículo en Wikipedia sobre Permutaciones y su generación que se parece bastante a la función de clasificación en papel de Myrvold y Ruskey .

Me parece que esto podría usarse en un generador de la misma manera que en otras respuestas para disminuir considerablemente el requisito de memoria. Solo recuerde que las permutaciones no estarán en orden lexicográfico.

 from __future__ import print_function def perm(n): p = [] for i in range(0,n+1): p.append(i) while True: for i in range(1,n+1): print(p[i], end=' ') print("") i = n - 1 found = 0 while (not found and i>0): if p[i]p[k]: k = k - 1 aux = p[i] p[i] = p[k] p[k] = aux for j in range(1,(ni)/2+1): aux = p[i+j] p[i+j] = p[n-j+1] p[n-j+1] = aux if not found: break perm(5) 

Aquí hay un algoritmo que funciona en una lista sin crear nuevas listas intermedias similares a la solución de Ber en https://stackoverflow.com/a/108651/184528 .

 def permute(xs, low=0): if low + 1 >= len(xs): yield xs else: for p in permute(xs, low + 1): yield p for i in range(low + 1, len(xs)): xs[low], xs[i] = xs[i], xs[low] for p in permute(xs, low + 1): yield p xs[low], xs[i] = xs[i], xs[low] for p in permute([1, 2, 3, 4]): print p 

Puede probar el código usted mismo aquí: http://repl.it/J9v

La belleza de la recursión:

 >>> import copy >>> def perm(prefix,rest): ... for e in rest: ... new_rest=copy.copy(rest) ... new_prefix=copy.copy(prefix) ... new_prefix.append(e) ... new_rest.remove(e) ... if len(new_rest) == 0: ... print new_prefix + new_rest ... continue ... perm(new_prefix,new_rest) ... >>> perm([],['a','b','c','d']) ['a', 'b', 'c', 'd'] ['a', 'b', 'd', 'c'] ['a', 'c', 'b', 'd'] ['a', 'c', 'd', 'b'] ['a', 'd', 'b', 'c'] ['a', 'd', 'c', 'b'] ['b', 'a', 'c', 'd'] ['b', 'a', 'd', 'c'] ['b', 'c', 'a', 'd'] ['b', 'c', 'd', 'a'] ['b', 'd', 'a', 'c'] ['b', 'd', 'c', 'a'] ['c', 'a', 'b', 'd'] ['c', 'a', 'd', 'b'] ['c', 'b', 'a', 'd'] ['c', 'b', 'd', 'a'] ['c', 'd', 'a', 'b'] ['c', 'd', 'b', 'a'] ['d', 'a', 'b', 'c'] ['d', 'a', 'c', 'b'] ['d', 'b', 'a', 'c'] ['d', 'b', 'c', 'a'] ['d', 'c', 'a', 'b'] ['d', 'c', 'b', 'a'] 
 def pzip(c, seq): result = [] for item in seq: for i in range(len(item)+1): result.append(item[i:]+c+item[:i]) return result def perm(line): seq = [c for c in line] if len(seq) <=1 : return seq else: return pzip(seq[0], perm(seq[1:])) 

Este algoritmo es el más efectivo, evita el paso de matrices y la manipulación en llamadas recursivas, funciona en Python 2, 3:

 def permute(items): length = len(items) def inner(ix=[]): do_yield = len(ix) == length - 1 for i in range(0, length): if i in ix: #avoid duplicates continue if do_yield: yield tuple([items[y] for y in ix + [i]]) else: for p in inner(ix + [i]): yield p return inner() 

Uso:

 for p in permute((1,2,3)): print(p) (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1) 

Generar todas las permutaciones posibles.

Estoy usando python3.4:

 def calcperm(arr, size): result = set([()]) for dummy_idx in range(size): temp = set() for dummy_lst in result: for dummy_outcome in arr: if dummy_outcome not in dummy_lst: new_seq = list(dummy_lst) new_seq.append(dummy_outcome) temp.add(tuple(new_seq)) result = temp return result 

Casos de prueba:

 lst = [1, 2, 3, 4] #lst = ["yellow", "magenta", "white", "blue"] seq = 2 final = calcperm(lst, seq) print(len(final)) print(final) 

Veo muchas iteraciones ocurriendo dentro de estas funciones recursivas, no exactamente una recursión pura

así que para aquellos de ustedes que no pueden cumplir con un solo bucle, aquí hay una solución totalmente recursiva burda, totalmente innecesaria

 def all_insert(x, e, i=0): return [x[0:i]+[e]+x[i:]] + all_insert(x,e,i+1) if i 

Otra solución:

 def permutation(flag, k =1 ): N = len(flag) for i in xrange(0, N): if flag[i] != 0: continue flag[i] = k if k == N: print flag permutation(flag, k+1) flag[i] = 0 permutation([0, 0, 0]) 

Para ahorrarle a la gente posibles horas de búsqueda y experimentación, aquí está la solución de permutaciones no recursivas en Python que también funciona con Numba (a partir del v. 0.41):

 @numba.njit() def permutations(A, k): r = [[i for i in range(0)]] for i in range(k): r = [[a] + b for a in A for b in r if (a in b)==False] return r permutations([1,2,3],3) [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 

Para dar una impresión sobre el rendimiento:

 %timeit permutations(np.arange(5),5) 243 µs ± 11.1 µs per loop (mean ± std. dev. of 7 runs, 1 loop each) time: 406 ms %timeit list(itertools.permutations(np.arange(5),5)) 15.9 µs ± 8.61 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) time: 12.9 s 

Por lo tanto, use esta versión solo si tiene que llamarla desde la función njitted, de lo contrario, prefiera la implementación de herramientas.

Mi solución de Python:

 def permutes(input,offset): if( len(input) == offset ): return [''.join(input)] result=[] for i in range( offset, len(input) ): input[offset], input[i] = input[i], input[offset] result = result + permutes(input,offset+1) input[offset], input[i] = input[i], input[offset] return result # input is a "string" # return value is a list of strings def permutations(input): return permutes( list(input), 0 ) # Main Program print( permutations("wxyz") ) 
 def permutation(word, first_char=None): if word == None or len(word) == 0: return [] if len(word) == 1: return [word] result = [] first_char = word[0] for sub_word in permutation(word[1:], first_char): result += insert(first_char, sub_word) return sorted(result) def insert(ch, sub_word): arr = [ch + sub_word] for i in range(len(sub_word)): arr.append(sub_word[i:] + ch + sub_word[:i]) return arr assert permutation(None) == [] assert permutation('') == [] assert permutation('1') == ['1'] assert permutation('12') == ['12', '21'] print permutation('abc') 

Salida: [‘abc’, ‘acb’, ‘bac’, ‘bca’, ‘cab’, ‘cba’]

Utilizando Counter

 from collections import Counter def permutations(nums): ans = [[]] cache = Counter(nums) for idx, x in enumerate(nums): result = [] for items in ans: cache1 = Counter(items) for id, n in enumerate(nums): if cache[n] != cache1[n] and items + [n] not in result: result.append(items + [n]) ans = result return ans permutations([1, 2, 2]) > [[1, 2, 2], [2, 1, 2], [2, 2, 1]] 

OTRO ENFOQUE (sin libs)

 def permutation(input): if len(input) == 1: return input if isinstance(input, list) else [input] result = [] for i in range(len(input)): first = input[i] rest = input[:i] + input[i + 1:] rest_permutation = permutation(rest) for p in rest_permutation: result.append(first + p) return result 

La entrada puede ser una cadena o una lista

 print(permutation('abcd')) print(permutation(['a', 'b', 'c', 'd'])) 

De esta manera es mejor que las alternativas que estoy viendo, échale un vistazo.

 def permutations(arr): if not arr: return print arr for idx, val in enumerate(arr): permutations(arr[:idx]+arr[idx+1:])