permutaciones - Haciendo todas las combinaciones posibles de una lista en python

permutaciones python

Question

Necesito poder hacer una lista que contenga todas las combinaciones posibles de una lista ingresada. Por ejemplo, la lista [1,2,3] debería devolver [1 [1,2] [1,3] 2 [2,3] 3 [1,2,3]] La lista no tiene que estar en ningún orden particular. En este sitio he encontrado muchas funciones usando las herramientas de iteración, pero esas son objetos que regresan cuando solo necesito una lista. Soy un principiante en la codificación de pitón por lo que cualquier pensamiento o idea sería muy apreciada.

Answer 1

El módulo itertools realmente devuelve generadores en lugar de listas, pero:

• Los generadores a menudo son más eficientes que las listas (especialmente si está generando una gran cantidad de combinaciones)
• Siempre puede convertir generadores a listas usando list(...) cuando realmente lo necesite.

Las funciones de chain y combinations de itertools funcionan bien , pero necesitas usar Python 2.6 o superior:

import itertools

def all_combinations(any_list):
    return itertools.chain.from_iterable(
        itertools.combinations(any_list, i + 1)
        for i in xrange(len(any_list)))

A continuación, puede llamar esto como tal:

# as a generator
all_combinations([1,2,3])  # --> <itertools.chain at 0x10ef7ce10>

# as a list
list(all_combinations([1,2,3]))  # --> [(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

# as a list of lists
[list(l) for l in all_combinations([1,2,3])]  # --> [[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Si no ha utilizado generadores antes, observe que los recorre como si fueran una lista, como esta:

# a generator returned instead of list
my_combinations = all_combinations([1,2,3])

# this would also work if `my_combinations` were a list
for c in my_combinations:
    print "Combo", c

"""
Prints:
  Combo (1,)
  Combo (2,)
  Combo (3,)
  Combo (1, 2)
  Combo (1, 3)
  Combo (2, 3)
  Combo (1, 2, 3)
"""

La diferencia de rendimiento puede ser dramática. Si compara el rendimiento, verá que el generador es mucho más rápido de crear:

# as a generator
all_combinations(range(25))  # timing: 100000 loops, best of 3: 2.53 µs per loop

# as a list
list(all_combinations(range(25)))  # timing: 1 loops, best of 3: 9.37 s per loop

Tenga en cuenta que todavía tomará un tiempo para iterar a través de todas las combinaciones en ambos casos, pero puede ser una gran ganancia para usted, especialmente si encuentra lo que está buscando desde el principio.

Answer 2

Las funciones del módulo itertools devuelven iteradores. Todo lo que necesita hacer para convertir estas listas en listas de llamadas list() el resultado.

Sin embargo, dado que necesitará llamar a itertools.combinations tres veces por separado (una para cada longitud diferente), puede usar list.extend para agregar todos los elementos del iterador a su lista final.

Pruebe lo siguiente:

import itertools
in_list = [1, 2, 3]
out_list = []
for i in range(1, len(in_list)+1):
    out_list.extend(itertools.combinations(in_list, i))

O como una lista de comprensión:

out_list = [c for i in range(len(in_list)) for c in itertools.combinations(in_list, i+1)]

Esto dará como resultado la siguiente lista:

[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Si desea listas en lugar de tuplas, y para convertir las tuplas de longitud única en solo el valor, puede hacer lo siguiente:

out_list = [x[0] if len(x) == 1 else list(x) for x in out_list]
# [1, 2, 3, [1, 2], [1, 3], [2, 3], [1, 2, 3]]

O para dejar los elementos individuales como listas:

out_list = map(list, out_list)

Answer 3

Podrías resolver tu problema usando itertools.combinations dentro de un bucle:

>>> l = [1,2,3]
>>> comb = []
>>> for i in range(len(l)):
...   comb += itertools.combinations(l,i+1)
... 
>>> comb
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]

Y si los quiere como una lista:

>>> comb_list = [ list(t) for t in comb ]
>>> comb_list
[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

EDITAR: El primer parámetro de combinaciones es el iterable y el segundo es la longitud de las tuplas resultantes (en este caso, va de 1 a len(l) ).

Más sobre combinaciones: http://docs.python.org/library/itertools.html#itertools.combinations

Answer 4

Simplemente use itertools.combinations . Por ejemplo:

import itertools

lst = [1, 2, 3]
combs = []

for i in xrange(1, len(lst)+1):
    combs.append(i)
    els = [list(x) for x in itertools.combinations(lst, i)]
    combs.append(els)

Ahora los combs tienen este valor:

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

Sí, es ligeramente diferente de la salida de muestra que proporcionó, pero en esa salida no estaba enumerando todas las combinaciones posibles.

Estoy enumerando el tamaño de la combinación antes de la lista real para cada tamaño, si lo que necesitas son simplemente las combinaciones (sin el tamaño, como aparece en tu resultado de muestra) y luego prueba con estas otras versiones del código:

import itertools

lst = [1, 2, 3]
combs = []

for i in xrange(1, len(lst)+1):
    els = [list(x) for x in itertools.combinations(lst, i)]
    combs.extend(els)

Ahora los combs tienen este valor:

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

Answer 5

l = [1,2,3]
combs = reduce(lambda x, y: list(itertools.combinations(l, y)) + x, range(len(l)+1), [])

Si quieres un oneliner