ti-enxame.com

Fazendo todas as combinações possíveis de uma lista

Eu preciso ser capaz de fazer uma lista que contenha todas as combinações possíveis de uma lista inserida. Por exemplo, a lista [1,2,3] deve retornar [1 [1,2] [1,3] 2 [2,3] 3 [1,2,3]] A lista não precisa estar em nenhuma ordem específica. Neste site, encontrei muitas funções usando o itertools, mas essas estão retornando objetos quando eu preciso apenas de um list.

43
Deano

Basta usar itertools.combinations . Por exemplo:

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)

Agora combs mantém este valor:

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

Sim, é um pouco diferente da saída de amostra que você forneceu, mas nessa saída você não estava listando todas as combinações possíveis.

Estou listando o tamanho da combinação antes da lista real de cada tamanho, se o que você precisa são simplesmente as combinações (sem o tamanho, como aparece na sua saída de amostra) e tente estas outras versões do 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)

Agora combs mantém este valor:

[[1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
52
Óscar López

O módulo itertools realmente retorna geradores em vez de listas, mas:

  • Os geradores geralmente são mais eficientes que as listas (especialmente se você estiver gerando um grande número de combinações)
  • Você sempre pode converter geradores em listas usando list(...) quando realmente precisar.

As funções chain e combinations de itertools funcionam bem, mas você precisa usar Python 2.6 ou 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)))

Você pode chamar isso assim:

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

Se você nunca usou geradores antes, observe que você os percorre como se fossem uma 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)
"""

A diferença de desempenho pode ser dramática. Se você comparar o desempenho, verá que o gerador é muito mais rápido para criar:

# 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

Observe que ainda levará algum tempo para percorrer todas as combinações em ambos os casos, mas pode ser uma grande vitória para você, especialmente se você encontrar o que está procurando desde o início.

11
Arel

As funções do módulo itertools retornam iteradores. Tudo o que você precisa fazer para convertê-los em listas é chamar list() no resultado.

No entanto, como você precisará ligar para itertools.combinations três vezes separadas (uma vez para cada comprimento diferente), você pode simplesmente usar list.extend para adicionar todos os elementos do iterador à sua lista final.

Tente o seguinte:

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

Ou como uma lista de compreensão:

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

Isso resultará na seguinte lista:

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

Se você deseja listas em vez de tuplas e converter as tuplas de comprimento único apenas no valor, faça o seguinte:

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

Ou, para deixar os itens únicos como listas:

out_list = map(list, out_list)
6
Andrew Clark

Você pode resolver seu problema usando itertools.combinations Dentro de um loop:

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

E se você os quiser como uma lista:

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

EDIT: O primeiro parâmetro de combinações é iterável e o segundo é o comprimento das tuplas resultantes (neste caso, indo de 1 para len(l)).

Mais sobre combinações: http://docs.python.org/library/itertools.html#itertools.combinations

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

Se você quer um forro.

3
Prafulla Mahesh Pallal

Eu acho que vale a pena resumir as outras respostas aqui em um exemplo simples Python 3 exemplo:

from itertools import chain, combinations

def all_combinations(array):
    return chain(*(list(combinations(array, i + 1)) for i in range(len(array))))

Isso retorna um iterável, para visualizar os valores:

>>> print(list(all_combinations((1, 2, 3))))
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
0
Ninjakannon