Obter o produto cartesiano de uma série de listas?

317

Como posso obter o produto cartesiano (todas as combinações possíveis de valores) de um grupo de listas?

Entrada:

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]

Saída desejada:

[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), (2, 'a', 5) ...]
ʞɔıu
fonte
24
esteja ciente de que "todas as combinações possíveis" não são exatamente o mesmo que "produto cartesiano", pois, nos produtos cartesianos, duplicatas são permitidas.
Triptych
7
Existe uma versão não duplicada do produto cartesiano?
KJW #
16
@KJW Sim,set(cartesian product)
NoBugs
5
Não deve haver duplicatas em um produto cartesiano, a menos que as listas de entrada contenham duplicatas. Se você não deseja duplicatas no produto cartesiano, use set(inputlist)sobre todas as suas listas de entrada. Não no resultado.
CamilB
@Triptych what? A definição padrão de um produto cartesiano é um conjunto. Por que tantas pessoas votam?
PascalIv 17/04

Respostas:

378

itertools.product

Disponível no Python 2.6.

import itertools

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]
for element in itertools.product(*somelists):
    print(element)

Qual é o mesmo que,

for element in itertools.product([1, 2, 3], ['a', 'b'], [4, 5]):
    print(element)
Tríptico
fonte
22
Você só deseja adicionar o caractere '*' se for necessário usar as listas somel variáveis, conforme fornecido pelo OP.
Brian buck
1
@jaska: product()gera nitems_in_a_list ** nlistselementos no resultado ( reduce(mul, map(len, somelists))). Não há razão para acreditar que produzir um único elemento não seja O(nlists)(amortizado), ou seja, a complexidade do tempo é a mesma que para loops aninhados simplesfor , por exemplo, para a entrada na pergunta :,nlists=3 número total de elementos no resultado: 3*2*2e cada elemento possui nlistsitens ( 3neste caso).
precisa saber é
2
Para que serve *antes de listas de som? O que isso faz?
Vineet Kumar Doshi
6
@VineetKumarDoshi: Aqui é usado para desmarcar uma lista em vários argumentos para a chamada de função. Leia mais aqui: stackoverflow.com/questions/36901/…
Moberg 15/15
4
Nota: Isso funciona apenas se cada lista contiver pelo menos um item
igo 13/09
84
import itertools
>>> for i in itertools.product([1,2,3],['a','b'],[4,5]):
...         print i
...
(1, 'a', 4)
(1, 'a', 5)
(1, 'b', 4)
(1, 'b', 5)
(2, 'a', 4)
(2, 'a', 5)
(2, 'b', 4)
(2, 'b', 5)
(3, 'a', 4)
(3, 'a', 5)
(3, 'b', 4)
(3, 'b', 5)
>>>
Jason Baker
fonte
38

Para Python 2.5 e mais antigo:

>>> [(a, b, c) for a in [1,2,3] for b in ['a','b'] for c in [4,5]]
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), 
 (2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5), 
 (3, 'b', 4), (3, 'b', 5)]

Aqui está uma versão recursiva de product()(apenas uma ilustração):

def product(*args):
    if not args:
        return iter(((),)) # yield tuple()
    return (items + (item,) 
            for items in product(*args[:-1]) for item in args[-1])

Exemplo:

>>> list(product([1,2,3], ['a','b'], [4,5])) 
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), 
 (2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5), 
 (3, 'b', 4), (3, 'b', 5)]
>>> list(product([1,2,3]))
[(1,), (2,), (3,)]
>>> list(product([]))
[]
>>> list(product())
[()]
jfs
fonte
A versão recursiva não funciona se alguns argsforem iteradores.
jfs
20

com itertools.product :

import itertools
result = list(itertools.product(*somelists))
SilentGhost
fonte
6
Para que serve *antes de listas de som?
Vineet Kumar Doshi
@VineetKumarDoshi "product (somelists)" é um produto cartesiano entre as sublistas, de maneira que o Python primeiro obtenha "[1, 2, 3]" como um elemento e depois obtenha outro elemento após o próximo comman e que seja quebra de linha, portanto, o primeiro produto termo é ([1, 2, 3],), semelhante ao segundo ([4, 5],) e então "[([1, 2, 3],), ([4, 5],), ( [6, 7],)] " . Se você deseja obter um produto cartesiano entre elementos dentro das tuplas, precisa informar ao Python com Asterisk sobre a estrutura das tuplas. Para o dicionário, você usa **. Mais aqui .
hhh
19

Eu usaria a compreensão da lista:

somelists = [
   [1, 2, 3],
   ['a', 'b'],
   [4, 5]
]

cart_prod = [(a,b,c) for a in somelists[0] for b in somelists[1] for c in somelists[2]]
user1035648
fonte
1
Eu realmente gosto dessa solução usando a compreensão da lista. Não sei por que não é mais votado, é tão simples.
llekn
20
@llekn porque o código parece estar corrigido no número de listas #
217 Rikimaru
11

Aqui está um gerador recursivo, que não armazena nenhuma lista temporária

def product(ar_list):
    if not ar_list:
        yield ()
    else:
        for a in ar_list[0]:
            for prod in product(ar_list[1:]):
                yield (a,)+prod

print list(product([[1,2],[3,4],[5,6]]))

Resultado:

[(1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6)]
Anurag Uniyal
fonte
1
Eles são armazenados na pilha, no entanto.
Quentin Pradet
@QuentinPradet, você quer dizer que um gerador def f(): while True: yield 1continuará aumentando seu tamanho de pilha à medida que o passarmos?
Anurag Uniyal 16/03/2015
@QuentinPradet sim, mas mesmo neste caso apenas a pilha necessário para profundidade máxima, não toda a lista, portanto, neste caso pilha de 3
Anurag Uniyal
É verdade, desculpe. Uma referência pode ser interessante. :)
Quentin Pradet
11

No Python 2.6 e acima, você pode usar 'itertools.product`. Nas versões mais antigas do Python, você pode usar o seguinte código equivalente (quase - consulte a documentação) da documentação , pelo menos como ponto de partida:

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

O resultado de ambos é um iterador; portanto, se você realmente precisar de uma lista para processamento posterior, use list(result).


fonte
De acordo com a documentação, a implementação real do itertools.product NÃO cria resultados intermediários, o que pode ser caro. O uso dessa técnica pode sair do controle rapidamente para listas de tamanho médio.
Triptych
4
Eu só posso apontar o OP para a documentação, e não ler para ele.
1
O código da documentação visa demonstrar o que a função do produto faz, não como uma solução alternativa para versões anteriores do Python.
Triptych
9

Embora já existam muitas respostas, gostaria de compartilhar alguns dos meus pensamentos:

Abordagem iterativa

def cartesian_iterative(pools):
  result = [[]]
  for pool in pools:
    result = [x+[y] for x in result for y in pool]
  return result

Abordagem Recursiva

def cartesian_recursive(pools):
  if len(pools) > 2:
    pools[0] = product(pools[0], pools[1])
    del pools[1]
    return cartesian_recursive(pools)
  else:
    pools[0] = product(pools[0], pools[1])
    del pools[1]
    return pools
def product(x, y):
  return [xx + [yy] if isinstance(xx, list) else [xx] + [yy] for xx in x for yy in y]

Abordagem Lambda

def cartesian_reduct(pools):
  return reduce(lambda x,y: product(x,y) , pools)
weiyixie
fonte
Em "Abordagem iterativa", por isso é resultado declarado como resultado = [[]] Eu sei que é list_of_list mas, em geral, mesmo se tivermos declarar list_of_list usamos [] e não [[]]
Sachin S
Sou um pouco novato em termos de soluções Pythonic. Você ou algum transeunte deve escrever a compreensão da lista na "abordagem iterativa" em loops separados?
Johnny Boy
4

Abordagem Recursiva:

def rec_cart(start, array, partial, results):
  if len(partial) == len(array):
    results.append(partial)
    return 

  for element in array[start]:
    rec_cart(start+1, array, partial+[element], results)

rec_res = []
some_lists = [[1, 2, 3], ['a', 'b'], [4, 5]]  
rec_cart(0, some_lists, [], rec_res)
print(rec_res)

Abordagem Iterativa:

def itr_cart(array):
  results = [[]]
  for i in range(len(array)):
    temp = []
    for res in results:
      for element in array[i]:
        temp.append(res+[element])
    results = temp

  return results

some_lists = [[1, 2, 3], ['a', 'b'], [4, 5]]  
itr_res = itr_cart(some_lists)
print(itr_res)
Jai
fonte
3

Uma pequena modificação na solução do gerador recursivo acima, com sabor variado:

def product_args(*args):
    if args:
        for a in args[0]:
            for prod in product_args(*args[1:]) if args[1:] else ((),):
                yield (a,) + prod

E, é claro, um invólucro que faz com que funcione exatamente da mesma forma que essa solução:

def product2(ar_list):
    """
    >>> list(product(()))
    [()]
    >>> list(product2(()))
    []
    """
    return product_args(*ar_list)

com um trade-off : verifica se a recursão deve quebrar em cada loop externo e um ganho : nenhum rendimento em chamada vazia, por exemplo product(()), o que eu suponho que seria semanticamente mais correto (consulte o doctest).

Quanto à compreensão da lista: a definição matemática se aplica a um número arbitrário de argumentos, enquanto a compreensão da lista pode lidar apenas com um número conhecido deles.

Mike Lu
fonte
2

Apenas para adicionar um pouco ao que já foi dito: se você usa o sympy, pode usar símbolos em vez de strings, o que os torna matematicamente úteis.

import itertools
import sympy

x, y = sympy.symbols('x y')

somelist = [[x,y], [1,2,3], [4,5]]
somelist2 = [[1,2], [1,2,3], [4,5]]

for element in itertools.product(*somelist):
  print element

Sobre o sympy .

Tyler Heers
fonte
1

Eu acredito que isso funciona:

def cartesian_product(L):  
   if L:
       return {(a,) + b for a in L[0] 
                        for b in cartesian_product(L[1:])}
   else:
       return {()}
Richard Samuelson
fonte
0

Abordagem Stonehenge:

def giveAllLists(a, t):
    if (t + 1 == len(a)):
        x = []
        for i in a[t]:
            p = [i]
            x.append(p)
        return x
    x = []

    out = giveAllLists(a, t + 1)
    for i in a[t]:

        for j in range(len(out)):
            p = [i]
            for oz in out[j]:
                p.append(oz)
            x.append(p)
    return x

xx= [[1,2,3],[22,34,'se'],['k']]
print(giveAllLists(xx, 0))

resultado:

[[1, 22, 'k'], [1, 34, 'k'], [1, 'se', 'k'], [2, 22, 'k'], [2, 34, 'k'], [2, 'se', 'k'], [3, 22, 'k'], [3, 34, 'k'], [3, 'se', 'k']]
Sina
fonte