¿Cómo obtener todas las combinaciones posibles de los elementos de una lista?
-
19-08-2019 - |
Pregunta
Tengo una lista con 15 números y necesito escribir un código que produzca las 32,768 combinaciones de esos números.
He encontrado algún código (buscando en Google) que aparentemente hace lo que estoy buscando, pero encontré el código bastante opaco y desconfío de usarlo. Además, tengo la sensación de que debe haber una solución más elegante.
Lo único que se me ocurre sería simplemente recorrer los enteros decimales 1 & # 8211; 32768 y convertirlos en binarios, y usar la representación binaria como filtro para seleccionar los números apropiados.
¿Alguien sabe de una mejor manera? Usando map ()
, ¿tal vez?
Solución
Eche un vistazo a itertools.combinations :
itertools.combinations(iterable, r)
Devuelve subsecuencias de longitud r de elementos de la entrada iterable.
Las combinaciones se emiten en orden de clasificación lexicográfica. Entonces, si el la entrada iterable está ordenada, la se producirán tuplas combinadas en orden ordenado.
¡Desde 2.6, las baterías están incluidas!
Otros consejos
Esta respuesta omitió un aspecto: el OP solicitó TODAS las combinaciones ... no solo las combinaciones de longitud " r " ;.
Por lo tanto, tendría que recorrer todas las longitudes " L " ;:
import itertools
stuff = [1, 2, 3]
for L in range(0, len(stuff)+1):
for subset in itertools.combinations(stuff, L):
print(subset)
O, si desea ponerse elegante (o doblar el cerebro de quien lea su código después de usted), puede generar la cadena de "combinaciones" () " generadores, e iterar a través de eso:
from itertools import chain, combinations
def all_subsets(ss):
return chain(*map(lambda x: combinations(ss, x), range(0, len(ss)+1)))
for subset in all_subsets(stuff):
print(subset)
Aquí hay una línea perezosa, que también usa itertools:
from itertools import compress, product
def combinations(items):
return ( set(compress(items,mask)) for mask in product(*[[0,1]]*len(items)) )
# alternative: ...in product([0,1], repeat=len(items)) )
Idea principal detrás de esta respuesta: hay 2 ^ N combinaciones, lo mismo que el número de cadenas binarias de longitud N. Para cada cadena binaria, elige todos los elementos correspondientes a un " 1 " ;.
items=abc * mask=###
|
V
000 ->
001 -> c
010 -> b
011 -> bc
100 -> a
101 -> a c
110 -> ab
111 -> abc
Cosas a considerar:
- Esto requiere que pueda llamar a
len (...)
enitems
(solución alternativa: siitems
es algo así como un iterable como un generador, conviértalo primero en una lista conitems = list (_itemsArg)
) - Esto requiere que el orden de iteración en
items
no sea aleatorio (solución alternativa: no se vuelva loco) - Esto requiere que los elementos sean únicos, o de lo contrario
{2,2,1}
y{2,1,1}
se colapsarán a{ 2,1}
(solución alternativa: usecollections.Counter
como un reemplazo directo paraset
; es básicamente un conjunto múltiple ... aunque es posible que necesite luego usetuple (sorted (Counter (...). elements ()))
si necesita que sea hashaable)
Demo
>>> list(combinations(range(4)))
[set(), {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}, {0}, {0, 3}, {0, 2}, {0, 2, 3}, {0, 1}, {0, 1, 3}, {0, 1, 2}, {0, 1, 2, 3}]
>>> list(combinations('abcd'))
[set(), {'d'}, {'c'}, {'c', 'd'}, {'b'}, {'b', 'd'}, {'c', 'b'}, {'c', 'b', 'd'}, {'a'}, {'a', 'd'}, {'a', 'c'}, {'a', 'c', 'd'}, {'a', 'b'}, {'a', 'b', 'd'}, {'a', 'c', 'b'}, {'a', 'c', 'b', 'd'}]
En los comentarios bajo el muy votado respuesta de @Dan H, se menciona el powerset ()
receta en la itertools
documentación & # 8212; incluido uno por Dan mismo . Sin embargo , hasta ahora nadie lo ha publicado como respuesta. Dado que es probablemente uno de los mejores, si no el mejor, enfoque del problema & # 8212; y dado un poco estímulo de otro comentarista, se muestra a continuación. La función produce todas combinaciones únicas de los elementos de la lista de cada longitud posible (incluidas las que contienen cero y todos los elementos).
Nota : Si el objetivo, sutilmente diferente, es obtener solo combinaciones de elementos únicos, cambie la línea s = list (iterable)
a s = list (set (iterable))
para eliminar cualquier elemento duplicado. En cualquier caso, el hecho de que el iterable
se convierta finalmente en una list
significa que funcionará con generadores (a diferencia de varias de las otras respuestas).
from itertools import chain, combinations
def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable) # allows duplicate elements
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
stuff = [1, 2, 3]
for i, combo in enumerate(powerset(stuff), 1):
print('combo #{}: {}'.format(i, combo))
Salida:
combo #1: ()
combo #2: (1,)
combo #3: (2,)
combo #4: (3,)
combo #5: (1, 2)
combo #6: (1, 3)
combo #7: (2, 3)
combo #8: (1, 2, 3)
Aquí hay uno que usa recursividad:
>>> import copy
>>> def combinations(target,data):
... for i in range(len(data)):
... new_target = copy.copy(target)
... new_data = copy.copy(data)
... new_target.append(data[i])
... new_data = data[i+1:]
... print new_target
... combinations(new_target,
... new_data)
...
...
>>> target = []
>>> data = ['a','b','c','d']
>>>
>>> combinations(target,data)
['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['a', 'b', 'd']
['a', 'c']
['a', 'c', 'd']
['a', 'd']
['b']
['b', 'c']
['b', 'c', 'd']
['b', 'd']
['c']
['c', 'd']
['d']
Esta línea le brinda todas las combinaciones (entre los elementos 0
y n
si la lista / conjunto original contiene elementos distintos de n
) y utiliza el método nativo itertools.combinations
:
Python 2
from itertools import combinations
input = ['a', 'b', 'c', 'd']
output = sum([map(list, combinations(input, i)) for i in range(len(input) + 1)], [])
Python 3
from itertools import combinations
input = ['a', 'b', 'c', 'd']
output = sum([list(map(list, combinations(input, i))) for i in range(len(input) + 1)], [])
El resultado será:
[[],
['a'],
['b'],
['c'],
['d'],
['a', 'b'],
['a', 'c'],
['a', 'd'],
['b', 'c'],
['b', 'd'],
['c', 'd'],
['a', 'b', 'c'],
['a', 'b', 'd'],
['a', 'c', 'd'],
['b', 'c', 'd'],
['a', 'b', 'c', 'd']]
Pruébelo en línea:
Estoy de acuerdo con Dan H en que Ben realmente pidió todas combinaciones. itertools.combinations ()
no proporciona todas las combinaciones.
Otro problema es que, si la entrada iterable es grande, quizás sea mejor devolver un generador en lugar de todo en una lista:
iterable = range(10)
for s in xrange(len(iterable)+1):
for comb in itertools.combinations(iterable, s):
yield comb
Puede generar todas las combinaciones de una lista en Python usando este código simple
import itertools
a = [1,2,3,4]
for i in xrange(0,len(a)+1):
print list(itertools.combinations(a,i))
El resultado sería:
[()]
[(1,), (2,), (3,), (4,)]
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
[(1, 2, 3, 4)]
Pensé que agregaría esta función para aquellos que buscan una respuesta sin importar itertools o cualquier otra biblioteca adicional.
def powerSet(items):
"""
Power set generator: get all possible combinations of a list’s elements
Input:
items is a list
Output:
returns 2**n combination lists one at a time using a generator
Reference: edx.org 6.00.2x Lecture 2 - Decision Trees and dynamic programming
"""
N = len(items)
# enumerate the 2**N possible combinations
for i in range(2**N):
combo = []
for j in range(N):
# test bit jth of integer i
if (i >> j) % 2 == 1:
combo.append(items[j])
yield combo
Uso simple del generador de rendimiento:
for i in powerSet([1,2,3,4]):
print (i, ", ", end="")
Salida del ejemplo de uso anterior:
[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4],
Aquí hay otra solución (una línea), que implica el uso de la función itertools.combinations
, pero aquí usamos una comprensión de lista doble (en oposición a un bucle for o sum):
def combs(x):
return [c for i in range(len(x)+1) for c in combinations(x,i)]
Demostración:
>>> combs([1,2,3,4])
[(),
(1,), (2,), (3,), (4,),
(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4),
(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4),
(1, 2, 3, 4)]
Este es un enfoque que puede transferirse fácilmente a todos los lenguajes de programación que admiten la recursión (sin itertools, sin rendimiento, sin comprensión de la lista) :
def combs(a):
if len(a) == 0:
return [[]]
cs = []
for c in combs(a[1:]):
cs += [c, c+[a[0]]]
return cs
>>> combs([1,2,3,4,5])
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], ..., [5, 4, 3, 2, 1]]
Se puede hacer usando itertools
Para permutaciones
Este método toma una lista como entrada y devuelve una lista de objetos de tuplas que contienen permutación de longitud L en forma de lista.
# A Python program to print all
# permutations of given length
from itertools import permutations
# Get all permutations of length 2
# and length 2
perm = permutations([1, 2, 3], 2)
# Print the obtained permutations
for i in list(perm):
print (i)
Para combinación
Este método toma una lista y una entrada r como entrada y devuelve una lista de objetos de tuplas que contienen todas las combinaciones posibles de longitud r en forma de lista.
# A Python program to print all
# combinations of given length
from itertools import combinations
# Get all combinations of [1, 2, 3]
# and length 2
comb = combinations([1, 2, 3], 2)
# Print the obtained combinations
for i in list(comb):
print (i)
vea esto
A continuación se muestra una " respuesta recursiva estándar " ;, similar a la otra respuesta similar https://stackoverflow.com/a/23743696 / 711085 . (Realmente no tenemos que preocuparnos por quedarnos sin espacio en la pila, ya que no hay forma de que podamos procesar todas las permutaciones de N!)
Visita cada elemento por turno, y lo toma o lo deja (podemos ver directamente la cardinalidad 2 ^ N de este algoritmo).
def combs(xs, i=0):
if i==len(xs):
yield ()
return
for c in combs(xs,i+1):
yield c
yield c+(xs[i],)
Demostración:
>>> list( combs(range(5)) )
[(), (0,), (1,), (1, 0), (2,), (2, 0), (2, 1), (2, 1, 0), (3,), (3, 0), (3, 1), (3, 1, 0), (3, 2), (3, 2, 0), (3, 2, 1), (3, 2, 1, 0), (4,), (4, 0), (4, 1), (4, 1, 0), (4, 2), (4, 2, 0), (4, 2, 1), (4, 2, 1, 0), (4, 3), (4, 3, 0), (4, 3, 1), (4, 3, 1, 0), (4, 3, 2), (4, 3, 2, 0), (4, 3, 2, 1), (4, 3, 2, 1, 0)]
>>> list(sorted( combs(range(5)), key=len))
[(),
(0,), (1,), (2,), (3,), (4,),
(1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3),
(2, 1, 0), (3, 1, 0), (3, 2, 0), (3, 2, 1), (4, 1, 0), (4, 2, 0), (4, 2, 1), (4, 3, 0), (4, 3, 1), (4, 3, 2),
(3, 2, 1, 0), (4, 2, 1, 0), (4, 3, 1, 0), (4, 3, 2, 0), (4, 3, 2, 1),
(4, 3, 2, 1, 0)]
>>> len(set(combs(range(5))))
32
Este código emplea un algoritmo simple con listas anidadas ...
# FUNCTION getCombos: To generate all combos of an input list, consider the following sets of nested lists...
#
# [ [ [] ] ]
# [ [ [] ], [ [A] ] ]
# [ [ [] ], [ [A],[B] ], [ [A,B] ] ]
# [ [ [] ], [ [A],[B],[C] ], [ [A,B],[A,C],[B,C] ], [ [A,B,C] ] ]
# [ [ [] ], [ [A],[B],[C],[D] ], [ [A,B],[A,C],[B,C],[A,D],[B,D],[C,D] ], [ [A,B,C],[A,B,D],[A,C,D],[B,C,D] ], [ [A,B,C,D] ] ]
#
# There is a set of lists for each number of items that will occur in a combo (including an empty set).
# For each additional item, begin at the back of the list by adding an empty list, then taking the set of
# lists in the previous column (e.g., in the last list, for sets of 3 items you take the existing set of
# 3-item lists and append to it additional lists created by appending the item (4) to the lists in the
# next smallest item count set. In this case, for the three sets of 2-items in the previous list. Repeat
# for each set of lists back to the initial list containing just the empty list.
#
def getCombos(listIn = ['A','B','C','D','E','F'] ):
listCombos = [ [ [] ] ] # list of lists of combos, seeded with a list containing only the empty list
listSimple = [] # list to contain the final returned list of items (e.g., characters)
for item in listIn:
listCombos.append([]) # append an emtpy list to the end for each new item added
for index in xrange(len(listCombos)-1, 0, -1): # set the index range to work through the list
for listPrev in listCombos[index-1]: # retrieve the lists from the previous column
listCur = listPrev[:] # create a new temporary list object to update
listCur.append(item) # add the item to the previous list to make it current
listCombos[index].append(listCur) # list length and append it to the current list
itemCombo = '' # Create a str to concatenate list items into a str
for item in listCur: # concatenate the members of the lists to create
itemCombo += item # create a string of items
listSimple.append(itemCombo) # add to the final output list
return [listSimple, listCombos]
# END getCombos()
Sé que es mucho más práctico usar itertools para obtener todas las combinaciones, pero puede lograr esto en parte con solo una lista de comprensión si así lo desea, dado que quieres codificar mucho
Para combinaciones de dos pares:
lambda l: [(a, b) for i, a in enumerate(l) for b in l[i+1:]]
Y, para combinaciones de tres pares, es tan fácil como esto:
lambda l: [(a, b, c) for i, a in enumerate(l) for ii, b in enumerate(l[i+1:]) for c in l[i+ii+2:]]
El resultado es idéntico al uso de itertools.combinations:
import itertools
combs_3 = lambda l: [
(a, b, c) for i, a in enumerate(l)
for ii, b in enumerate(l[i+1:])
for c in l[i+ii+2:]
]
data = ((1, 2), 5, "a", None)
print("A:", list(itertools.combinations(data, 3)))
print("B:", combs_3(data))
# A: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]
# B: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]
Sin usar itertools:
def combine(inp):
return combine_helper(inp, [], [])
def combine_helper(inp, temp, ans):
for i in range(len(inp)):
current = inp[i]
remaining = inp[i + 1:]
temp.append(current)
ans.append(tuple(temp))
combine_helper(remaining, temp, ans)
temp.pop()
return ans
print(combine(['a', 'b', 'c', 'd']))
Aquí hay dos implementaciones de itertools.combinations
Uno que devuelve una lista
def combinations(lst, depth, start=0, items=[]):
if depth <= 0:
return [items]
out = []
for i in range(start, len(lst)):
out += combinations(lst, depth - 1, i + 1, items + [lst[i]])
return out
Uno devuelve un generador
def combinations(lst, depth, start=0, prepend=[]):
if depth <= 0:
yield prepend
else:
for i in range(start, len(lst)):
for c in combinations(lst, depth - 1, i + 1, prepend + [lst[i]]):
yield c
Tenga en cuenta que se recomienda proporcionar una función auxiliar a aquellos porque el argumento de anteponer es estático y no cambia con cada llamada
print([c for c in combinations([1, 2, 3, 4], 3)])
# [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
# get a hold of prepend
prepend = [c for c in combinations([], -1)][0]
prepend.append(None)
print([c for c in combinations([1, 2, 3, 4], 3)])
# [[None, 1, 2, 3], [None, 1, 2, 4], [None, 1, 3, 4], [None, 2, 3, 4]]
Este es un caso muy superficial, pero más vale prevenir que curar
¿Qué tal esto? ... usó una cadena en lugar de una lista, pero lo mismo ... la cadena se puede tratar como una lista en Python:
def comb(s, res):
if not s: return
res.add(s)
for i in range(0, len(s)):
t = s[0:i] + s[i + 1:]
comb(t, res)
res = set()
comb('game', res)
print(res)
Combinación de itertools
import itertools
col_names = ["aa","bb", "cc", "dd"]
all_combinations = itertools.chain(*[itertools.combinations(col_names,i+1) for i,_ in enumerate(col_names)])
print(list(all_combinations))
Gracias
Sin itertools
en Python 3 podría hacer algo como esto:
def combinations(arr, carry):
for i in range(len(arr)):
yield carry + arr[i]
yield from combinations(arr[i + 1:], carry + arr[i])
donde inicialmente carry = " " ;.
Uso de la comprensión de la lista:
def selfCombine( list2Combine, length ):
listCombined = str( ['list2Combine[i' + str( i ) + ']' for i in range( length )] ).replace( "'", '' ) \
+ 'for i0 in range(len( list2Combine ) )'
if length > 1:
listCombined += str( [' for i' + str( i ) + ' in range( i' + str( i - 1 ) + ', len( list2Combine ) )' for i in range( 1, length )] )\
.replace( "', '", ' ' )\
.replace( "['", '' )\
.replace( "']", '' )
listCombined = '[' + listCombined + ']'
listCombined = eval( listCombined )
return listCombined
list2Combine = ['A', 'B', 'C']
listCombined = selfCombine( list2Combine, 2 )
La salida sería:
['A', 'A']
['A', 'B']
['A', 'C']
['B', 'B']
['B', 'C']
['C', 'C']
Esta es mi implementación
def get_combinations(list_of_things):
"""gets every combination of things in a list returned as a list of lists
Should be read : add all combinations of a certain size to the end of a list for every possible size in the
the list_of_things.
"""
list_of_combinations = [list(combinations_of_a_certain_size)
for possible_size_of_combinations in range(1, len(list_of_things))
for combinations_of_a_certain_size in itertools.combinations(list_of_things,
possible_size_of_combinations)]
return list_of_combinations
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = range(r)
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
x = [2, 3, 4, 5, 1, 6, 4, 7, 8, 3, 9]
for i in combinations(x, 2):
print i
Si alguien está buscando una lista inversa, como yo estaba:
stuff = [1, 2, 3, 4]
def reverse(bla, y):
for subset in itertools.combinations(bla, len(bla)-y):
print list(subset)
if y != len(bla):
y += 1
reverse(bla, y)
reverse(stuff, 1)