permutaciones - crear todas las combinaciones posibles python

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

Question

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

Answer 1

Aquí hay un algoritmo que funciona en una lista sin crear nuevas listas intermedias similares a la solución de Ber en https://.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

Answer 2

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

Answer 3

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.

Answer 4

El siguiente código es una permutación in situ de una lista determinada, implementada como un generador. Dado que 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

Answer 5

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

Answer 6

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

Answer 7

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)

Answer 8

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

Answer 9

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)

Answer 10

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

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

Perdone mi analfabetismo con 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 recuerda que las permutaciones no estarán en orden lexicográfico.

Answer 15

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]

Answer 16

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

Answer 17

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 del 0 al 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.

Answer 18

Veo mucha iteración dentro de estas funciones recursivas, no exactamente una recursión pura ...

así que para aquellos de ustedes que no pueden cumplir incluso 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<len(x)+1 else []
def for_each(X, e):
return all_insert(X[0], e) + for_each(X[1:],e) if X else []
def permute(x):
return [x] if len(x) < 2 else for_each( permute(x[1:]) , x[0])
perms = permute([1,2,3])

Answer 19

Y en Python 2.6 en adelante:

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

(devuelto como un generador. Utilice la list(permutations(l)) para devolver como una lista.)

Answer 20

para Python podemos usar itertools e importar permutaciones y combinaciones para resolver su problema

from itertools import product, permutations
A = ([1,2,3])
print (list(permutations(sorted(A),2)))

Answer 21

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 ella misma):

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 22

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

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)

Answer 23

#!/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 Computer Algorithms de Horowitz, Sahni y Rajasekeran .

Answer 24

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

Answer 25

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

Answer 26

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

Answer 27

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[i+1]:
found = 1
else:
i = i - 1
k = n
while p[i]>p[k]:
k = k - 1
aux = p[i]
p[i] = p[k]
p[k] = aux
for j in range(1,(n-i)/2+1):
aux = p[i+j]
p[i+j] = p[n-j+1]
p[n-j+1] = aux
if not found:
break
perm(5)

Answer 28

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