Como obter todas as combinações possíveis dos elementos de uma lista?

423

Eu tenho uma lista com 15 números e preciso escrever um código que produza todas as 32.768 combinações desses números.

Encontrei algum código (do Google) que aparentemente faz o que estou procurando, mas achei o código bastante opaco e desconfio de usá-lo. Além disso, sinto que deve haver uma solução mais elegante.

A única coisa que me ocorre seria apenas percorrer os números decimais de 1 a 32768 e convertê-los em binários, e usar a representação binária como um filtro para selecionar os números apropriados.

Alguém sabe de uma maneira melhor? Usando map(), talvez?

Ben
fonte
9
Os leitores devem observar que se os itens da lista são exclusivos é uma consideração extremamente importante, pois muitos algoritmos irão sobrepor algum subconjunto (por exemplo, 'abccc' -> ['', 'a', 'b', 'c', 'c' ., 'c', 'ac', 'ac', 'ac', ...] uma solução fácil é apenas empurrar todos os elementos de um conjunto antes de começar suas permutações.
ninjagecko
@ninjagecko O uso da biblioteca Set não é eficiente, pois cada um é O (n) na melhor das hipóteses. Assim, adicionar n funções a um conjunto é realmente O (n ^ 2)!
Scott Biggs
Ao ler atentamente a pergunta, parece que o OP está pedindo o PowerSet de sua lista de 15 números, nem todas as combinações. Eu acho que pode ser por isso que as respostas estão por todo o lado.
Scott Biggs
@ Scott Biggs: você tem certeza de que está falando sobre Python aqui? As inserções e pesquisas de conjunto são maiúsculas e minúsculas O (1). Eles são como dicionários. Eles usam hash. O Python não possui uma biblioteca de conjuntos especial (está na biblioteca padrão). Estamos inserindo números aqui, não funções. (Ainda seria ineficiente usar memória O (2 ^ n); a solução apropriada para pessoas que desejam combinações em vez do conjunto de potências é uma implementação recursiva simples ou productetc.)
ninjagecko

Respostas:

467

Dê uma olhada em itertools.combinations :

itertools.combinations(iterable, r)

Retorna r subsequências de comprimento dos elementos da entrada iterável.

As combinações são emitidas em ordem de classificação lexicográfica. Portanto, se a entrada iterável for classificada, as tuplas de combinação serão produzidas em ordem de classificação.

Desde 2.6, as pilhas estão incluídas!

James Brady
fonte
31
você pode apenas listar tudo. list(itertools.combinations(iterable, r))
Silgon 14/09/17
1
existe algo que não exija r, isto é, combinações de qualquer subsequência de comprimento de elementos.
mLstudent33
630

Essa resposta perdeu um aspecto: o OP solicitou TODAS as combinações ... não apenas as combinações de comprimento "r".

Então você teria que 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ê quiser ficar esnobe (ou torcer o cérebro de quem lê seu código depois de você) - você pode gerar a cadeia de geradores de "combinações ()" e iterar com isso:

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)
Dan H
fonte
42
Obrigado pelo apoio! Nas semanas desde que publiquei a resposta acima, descobri que o NOME do conceito para o que Ben está procurando é o "conjunto de poderes" do conjunto original de 15 itens. De fato, um exemplo de implementação é dado na página de documento python "itertools" padrão: docs.python.org/library/itertools.html (grep para "powerset").
Dan H
38
Para quem lê até agora: A powerset()função geradora na seção de receitas da itertoolsdocumentação é mais simples, potencialmente usa menos memória e provavelmente é mais rápida que a implementação mostrada aqui.
27616 martineau
É possível gerar todas as combinações em ordem lexicográfica?
guik
@ guik: tenho 99% de certeza de que itertools.combinationspreserva a ordem dos itens nas listas que produz. Assim, se a entrada for classificada lexicamente, cada uma das saídas também será.
11558 Dan H -
Sim, itertools.combinationsgera as combinações de k entre n em ordem lexicográfica, mas nem todas as combinações até k entre n. powersetgera todas as combinações até k, mas não em ordem lexicográfica, tanto quanto eu a entendo: powerset ([1,2]) -> [(), (1,), (2,), (1, 2)] . Não deveria ser: [(), (1,), (1, 2), (2,)]?
guik
52

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

Ideia principal por trás desta resposta: existem 2 ^ N combinações - o mesmo que o número de cadeias 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

Coisas a considerar:

  • Isto requer que você pode chamar len(...)em items(solução: se itemsé algo como um iterável como um gerador, transformá-lo em uma lista pela primeira vez com items=list(_itemsArg))
  • Isso requer que a ordem da iteração itemsnão seja aleatória (solução alternativa: não fique louco)
  • Isto requer que os itens são originais, ou então {2,2,1}e {2,1,1}serão ambos colapso a {2,1}(solução alternativa: o uso collections.Countercomo um substituto para set, é basicamente um multiset ... embora você pode precisar de usar mais tarde tuple(sorted(Counter(...).elements()))se você precisa que ele seja Hashable)

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'}]
ninjagecko
fonte
46

Nos comentários sob a resposta altamente votada por @Dan H, é mencionada a powerset()receita na itertoolsdocumentação - incluindo uma do próprio Dan . No entanto , até agora ninguém postou como resposta. Como é provavelmente uma das melhores, se não a melhor, para o problema - e com um pouco de incentivo de outro comentarista, é mostrado abaixo. A função produz todas as combinações exclusivas dos elementos da lista de todos os comprimentos possíveis (incluindo aqueles que contêm zero e todos os elementos).

Nota : Se o, sutilmente diferente, o objetivo é obter apenas as combinações de elementos únicos, altere a linha s = list(iterable)para s = list(set(iterable))eliminar quaisquer elementos duplicados. Independentemente disso, o fato de iterablefinalmente ser transformado em um listmeio funcionará com geradores (ao contrário de várias das 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))

Resultado:

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)
Martineau
fonte
Para que serve a list()conversão?
AMC
@ Alexander: Para permitir que o comprimento do iterável seja determinado.
martineau
36

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']
darxtrix
fonte
Isso pode ser modificado para retornar uma lista de listas em vez de imprimir?
precisa
@JamesVickery sim, você pode olhar para qualquer um fazer uma fora lista da função e acrescentar a isso, ou (melhor) fazer a função de um gerador, ter um olhar para o 'rendimento' palavra-chave :)
Dangercrow
new_data = copy.copy(data)- esta linha é redundante, tanto quanto eu vejo, ele não influencia em nada
Dmitriy Fialkovskiy
31

Essa linha fornece todas as combinações (entre 0e nitens, se a lista / conjunto original contiver nelementos distintos) 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 online:

http://ideone.com/COghfX

Mathieu Rodic
fonte
Isso é uma permutação #
28416 AdHominem
15
@ AdHominem: não, não é. É uma lista de todas as combinações. Permutações incluiriam, por exemplo ['b', 'a'].
precisa saber é o seguinte
TypeError: can only concatenate list (not "map") to list
0x48piraj 06/02/19
@ 0x48piraj: obrigado por perceber, eu editei minha resposta consequentemente!
Mathieu Rodic
21

Eu concordo com Dan H que Ben realmente pediu todas as combinações. itertools.combinations()não fornece todas as combinações.

Outra questão é que, se a entrada iterável for grande, talvez seja melhor retornar 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
HongboZhu
fonte
1
Belo exemplo. Eu amo geradores ... e eu amo Python por tê-los! Este exemplo possui apenas um objeto de combinações () por vez e gera uma das combinações por vez. (Talvez você queira adicionar o bloco def em torno disso - como um exemplo de uso.) Observe que minha implementação (com chain (), dada acima) não é muito pior: é verdade que cria todos os geradores len (iteráveis) em uma vez ... mas NÃO cria todas as combinações de 2 ** len (iteráveis) de uma só vez, pois - no meu entendimento - a cadeia "usa" o primeiro gerador antes de extrair os seguintes.
Dan H
18

Essa é uma abordagem que pode ser facilmente transferida para todas as linguagens de programação que suportam recursão (sem ferramentas, sem rendimento, sem compreensão de 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]]
Jonathan R
fonte
Ah! Implementação agradável. Reconheço HEAD = a [0], TAIL = a [1:] do Prolog. Ou carro = a [0], cdr = a [1:] do Lisp. Gostaria de saber se poderíamos usar memorização aqui ...
Javier Ruiz
Verdade. A fatia da lista é O (k), onde k é o comprimento da fatia. Eu acho que alguém poderia acelerar isso fazendo uma pesquisa em um mapa que tornaria O (1) em todas as execuções, exceto a primeira. Observe que essa implementação não deve ser referenciada para desempenho. Para isso existem melhores implementações. Essa implementação é apenas para simplicidade e portabilidade para a maioria dos outros idiomas.
Jonathan R
14

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

O 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)]
saimadhu.polamuri
fonte
Erro neste código: não retorna o conjunto vazio. Pode significar intervalo (0, ...), mas não foi testado. edit : fui em frente e editei sua resposta para corrigi-la.
Ninjagecko
13

Eu pensei em adicionar essa função para aqueles que procuram uma resposta sem importar ferramentas de ferramentas 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

Uso simples do gerador de rendimento:

for i in powerSet([1,2,3,4]):
    print (i, ", ",  end="")

Exemplo de saída do uso acima:

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


fonte
Eu acho que essa é uma solução muito legal.
GREENTEC
8

Aqui está mais uma solução (one-liner), envolvendo o uso da itertools.combinationsfunção, mas aqui usamos uma compreensão de lista dupla (em oposição a um loop ou soma for):

def combs(x):
    return [c for i in range(len(x)+1) for c in combinations(x,i)]

Demo:

>>> 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)]
ninjagecko
fonte
5
from itertools import permutations, combinations


features = ['A', 'B', 'C']
tmp = []
for i in range(len(features)):
    oc = combinations(features, i + 1)
    for c in oc:
        tmp.append(list(c))

resultado

[
 ['A'],
 ['B'],
 ['C'],
 ['A', 'B'],
 ['A', 'C'],
 ['B', 'C'],
 ['A', 'B', 'C']
]
Andrew Li
fonte
4

Abaixo está uma "resposta recursiva padrão", semelhante à outra resposta semelhante https://stackoverflow.com/a/23743696/711085 . (Realisticamente, não precisamos nos preocupar em ficar sem espaço na pilha, pois não há como processar todas as permutações do N!).

Ele visita todos os elementos por sua vez e o pega ou sai (podemos ver diretamente a cardinalidade 2 ^ N 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],)

Demo:

>>> 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
ninjagecko
fonte
2

Usando a 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 )

A saída seria:

['A', 'A']
['A', 'B']
['A', 'C']
['B', 'B']
['B', 'C']
['C', 'C']
zmk
fonte
4
Esta proposta é fazer a manipulação de strings para criar conjuntos?!?! Santo corvo .... E: não está retornando o conjunto de potência, mas algo como combinações_com_replocamento (). (Veja docs.python.org/library/… )
Dan H
Isso de fato faz o mesmo que combinado_com_replocamento () , mas pelo menos na minha caixa isso é executado um pouco mais rápido que o itertools . O que posso dizer, eu gosto de compreender listas.
Zmk
1
Obrigado pela resposta! Que tal criar listCombined com listas invertidas, como ['A', 'A'], ['A', 'B'], ['A', 'C'], ['B', 'A'], [ 'B', 'B'], ['B', 'C'], ['C', 'A'], ['C', 'B'] e ['C', 'C'] que incluem tudo?
21415 Karyo
Muito interessante, mas meu python não é capaz de entender as sutilezas aqui. Existe algo especial sobre o uso de listCombined em diferentes escopos e o fato de o loop for estar em uma linha? Estou tentando portar isso para Java com pouca sorte.
Scott Biggs
2

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()
TiPS
fonte
Portanto, o que esse código parece fazer é retornar [listOfCombinations, listOfCombinationsGroupedBySize]. Infelizmente, quando executado com a entrada demo, ele fornece 63 elementos em vez de 64; parece estar faltando o conjunto vazio (neste caso, a sequência vazia "").
Ninjagecko 13/09/2015
2

Sei que é muito mais prático usar as ferramentas para obter todas as combinações, mas você pode conseguir isso em parte apenas com compreensão de lista, se assim o desejar, desde que você deseje codificar muito

Para combinações de dois pares:

    lambda l: [(a, b) for i, a in enumerate(l) for b in l[i+1:]]


E, para combinações de três pares, é tão fácil quanto 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 uso 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)]
Cynadyde
fonte
2

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']))
Pradeep Vairamani
fonte
2

Aqui estão duas implementações de itertools.combinations

Um que retorna uma 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

Um 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

Observe que é aconselhável fornecer uma função auxiliar àqueles, porque o argumento de prefpend é estático e não é alterado a 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

Modar
fonte
2

Que tal isso .. usou uma string em vez de list, mas a mesma coisa .. string pode ser tratada 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)
Apurva Singh
fonte
2

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

obrigado

Abhishek
fonte
2

Sem itertools no Python 3 você poderia fazer algo assim:

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 = "".

Laurynas Tamulevičius
fonte
2

3 funções:

  1. todas as combinações de lista de n elementos
  2. todas as combinações de n elementos listam onde a ordem não é distinta
  3. todas as permutações
import sys

def permutations(a):
    return combinations(a, len(a))

def combinations(a, n):
    if n == 1:
        for x in a:
            yield [x]
    else:
        for i in range(len(a)):
            for x in combinations(a[:i] + a[i+1:], n-1):
                yield [a[i]] + x

def combinationsNoOrder(a, n):
    if n == 1:
        for x in a:
            yield [x]
    else:
        for i in range(len(a)):
            for x in combinationsNoOrder(a[:i], n-1):
                yield [a[i]] + x

if __name__ == "__main__":
    for s in combinations(list(map(int, sys.argv[2:])), int(sys.argv[1])):
        print(s)
Alan Swindells
fonte
Gosto muito disto!!! Obrigado!!! As funções combinatórias do Python são um pouco estranhas. Em matemática, a função "combinações" seria Variações, e "combinaçõesNoOrder" são na verdade combinações. Eu acho que isso confunde as pessoas que chegam ao python do ramo da matemática, como aconteceu comigo desta vez. Enfim, uma ótima solução, muito obrigado!
Đumić Branislav
1

Esta é a 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
Andres Ulloa
fonte
1
Qual é a sua implementação resolvendo melhor do que as implementações anteriores postadas aqui.
precisa saber é o seguinte
0

Você também pode usar a função powerset do excelente more_itertoolspacote.

from more_itertools import powerset

l = [1,2,3]
list(powerset(l))

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

Também podemos verificar se ele atende aos requisitos do OP

from more_itertools import ilen

assert ilen(powerset(range(15))) == 32_768
Jarno
fonte
-1
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
Anoop
fonte
1
Se eu estiver certo, este é o código exato copiado da documentação do python [ docs.python.org/3.6/library/itertools.html ]. Em caso afirmativo, ref consulte a fonte.
GabrielChu
abordagem interessante
Pelos
-1

Se alguém está procurando uma lista invertida, como eu:

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)
Expat C
fonte
-1
flag = 0
requiredCals =12
from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)  # allows duplicate elements
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

stuff = [2,9,5,1,6]
for i, combo in enumerate(powerset(stuff), 1):
    if(len(combo)>0):
        #print(combo , sum(combo))
        if(sum(combo)== requiredCals):
            flag = 1
            break
if(flag==1):
    print('True')
else:
    print('else')
Priyansh gupta
fonte