Como obter todas as possíveis combinações de elementos de uma lista?
-
19-08-2019 - |
Pergunta
Eu tenho uma lista com 15 números, e eu preciso escrever algum código que produz todos os 32.768 combinações desses números.
Eu encontrei alguns código (por googling) que, aparentemente, faz o que eu estou procurando, mas eu achei o código bastante opaco e estou desconfiado de usá-lo. Além disso, eu tenho um sentimento que deve haver uma solução mais elegante.
A única coisa que me ocorre seria apenas para percorrer os números inteiros decimais 1-32768 e converter aqueles a binário, e usar a representação binária como um filtro para escolher os números apropriados.
Alguém sabe de uma maneira melhor? Usando map()
, talvez?
Solução
Tenha um olhar em itertools.combinations :
itertools.combinations(iterable, r)
Retorno subsequ�ncias comprimento r de elementos de a entrada iterable.
As combinações são emitidos na ordem de classificação lexicográfica. Assim, se o input iterable é ordenada, o tuplos combinação vai ser produzido em ordem de classificação.
Desde 2.6, as baterias estão incluídas!
Outras dicas
Esta resposta perdeu um aspecto:. o OP pediu para todas as combinações ... não apenas combinações de comprimento "r"
Assim que você quer ter de percorrer todos os comprimentos "L":
import itertools
stuff = [1, 2, 3]
for L in range(0, len(stuff)+1):
for subset in itertools.combinations(stuff, L):
print(subset)
Ou - se você deseja obter snazzy (ou dobrar o cérebro de quem lê o seu código depois de você) - você pode gerar a cadeia de "combinações ()" geradores e iterate através de que:
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)
Aqui está um one-liner preguiçoso, também usando 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)) )
A idéia principal por trás dessa resposta: existem 2 ^ n combinações - mesmo que o número de strings binárias de comprimento N. Para cada cadeia binária, você escolhe todos os elementos correspondentes a um "1"
.items=abc * mask=###
|
V
000 ->
001 -> c
010 -> b
011 -> bc
100 -> a
101 -> a c
110 -> ab
111 -> abc
As coisas a considerar:
- Isto requer que você pode chamar
len(...)
emitems
(solução alternativa: seitems
é algo como um iterável como um gerador, transformá-lo em uma lista pela primeira vez comitems=list(_itemsArg)
) - Isto requer que a ordem de iteração em
items
não é aleatória (solução alternativa: não ser insano) - Isto requer que os itens são originais, ou então
{2,2,1}
e{2,1,1}
serão ambos colapso para{2,1}
(solução alternativa: utilizaçãocollections.Counter
como um substituto paraset
, é basicamente um multiset ... embora você pode precisar detuple(sorted(Counter(...).elements()))
uso posterior se você precisa que ele seja Hashable)
Demonstração
>>> 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'}]
Em comentários sob o altamente upvoted resposta por @ Dan H, menção é feita da receita powerset()
na documentação itertools
-incluindo um por Dan . No entanto , até agora ninguém postou-lo como uma resposta. Desde que é provavelmente um dos melhores se não a melhor abordagem para o problema e dado um pouco incentivo de outro comentarista, é mostrado abaixo. A função produz
Nota ??strong>: Se o, sutilmente diferente, o objetivo é obter apenas as combinações de elementos únicos, altere o s = list(iterable)
linha para s = list(set(iterable))
para eliminar quaisquer elementos duplicados. Independentemente disso, o fato de que o iterable
é finalmente se transformou em um meio list
ele vai trabalhar com geradores (ao contrário de vários de outras respostas).
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))
Output:
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)
Aqui está um usando recursão:
>>> 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']
Este one-liner dá-lhe todas as combinações (entre os itens 0
e n
se o original lista / conjunto contém elementos distintos n
) e usa o 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)], [])
A saída 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']]
Experimente on-line:
Eu concordo com Dan H que Ben fato pediu todas combinações. itertools.combinations()
não dá todas as combinações.
Outra questão é, se a entrada iterable é grande, talvez seja melhor voltar um gerador em vez de tudo em uma lista:
iterable = range(10)
for s in xrange(len(iterable)+1):
for comb in itertools.combinations(iterable, s):
yield comb
Você pode gerar todas as combinações de uma lista em python usando este código simples
import itertools
a = [1,2,3,4]
for i in xrange(0,len(a)+1):
print list(itertools.combinations(a,i))
resultado seria:
[()]
[(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)]
Eu pensei que eu gostaria de acrescentar essa função para aqueles que procuram uma resposta sem importar itertools ou quaisquer outras bibliotecas extras.
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
Simples Rendimento Gerador de Uso:
for i in powerSet([1,2,3,4]):
print (i, ", ", end="")
A saída de exemplo Uso acima:
[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [2, 4] [3, 4] [2, 3, 4] [1, 4], [1, 2, 4], [1, 3, 4], [1, 2, 3, 4],
Aqui está ainda outra solução (one-liner), envolvendo usando a função itertools.combinations
, mas aqui nós usamos uma lista compreensão dupla (em oposição a um loop for ou soma):
def combs(x):
return [c for i in range(len(x)+1) for c in combinations(x,i)]
Demonstração:
>>> 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)]
Esta é uma abordagem que pode ser facilmente transferidos para todas as linguagens de programação que suportam recursão (sem itertools, nenhum rendimento, nenhuma compreensão da 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]]
Pode ser feito usando itertools
Para permutações
Este método tem uma lista como entrada e retorno de uma lista de objectos de tuplos que contêm permutação de comprimento L, em uma 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 Combinação
Este método tem uma lista e uma entrada r como entrada e retorno de uma lista de objectos de tuplos que contêm todas as combinações possíveis de comprimento r em uma 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)
Abaixo está uma "resposta recursiva padrão", similar à outra resposta semelhante https://stackoverflow.com/a/23743696/ 711085 . (Nós não realisticamente precisa se preocupar em ficar sem espaço de pilha já que não há maneira de podermos processar toda N! Permutações.)
Visite cada elemento, por sua vez, e quer leva-lo ou deixa-lo (podemos ver diretamente o 2 ^ N cardinalidade deste 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],)
Demonstração:
>>> 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 emprega um algoritmo simples, com listas aninhadas ...
# 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()
Eu sei que é muito mais prático usar itertools para obter o todas as combinações, mas você pode conseguir isso, em parte, com apenas compreensão da lista, se assim acontecer a desejar, concedido você quiser código muito
Para combinações de dois pares:
lambda l: [(a, b) for i, a in enumerate(l) for b in l[i+1:]]
E, por combinações de três pares, é tão simples como isto:
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:]]
O resultado é idêntico ao usar 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)]
Sem 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']))
Aqui estão duas implementações de itertools.combinations
Um que retorna uma lista ??p>
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
Uma retorna um gerador
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
Por favor, note que o fornecimento de uma função auxiliar àqueles é aconselhável porque o argumento preceder é estático e não está mudando com cada chamada
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 é um caso muito superficial, mas melhor prevenir do que remediar
Como sobre isso .. usado uma corda em vez de lista, mas mesma coisa .. corda pode ser tratado como uma lista em 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)
A combinação 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))
Graças
Sem itertools
em Python 3 você poderia fazer algo parecido com isto:
def combinations(arr, carry):
for i in range(len(arr)):
yield carry + arr[i]
yield from combinations(arr[i + 1:], carry + arr[i])
onde inicialmente carry = "".
Usando compreensão da 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 )
Saída seria:
['A', 'A']
['A', 'B']
['A', 'C']
['B', 'B']
['B', 'C']
['C', 'C']
Esta é minha implementação
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
Se alguém está procurando uma lista invertida, como se eu fosse:
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)