Dapatkan produk kartesius dari serangkaian daftar?

317

Bagaimana saya bisa mendapatkan produk Cartesian (setiap kemungkinan kombinasi nilai) dari sekelompok daftar?

Memasukkan:

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

Output yang diinginkan:

[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), (2, 'a', 5) ...]
ʞɔıu
sumber
24
perlu diketahui bahwa 'setiap kombinasi yang mungkin' tidak sama dengan 'produk Cartesian', karena dalam produk Cartesian, duplikat diperbolehkan.
Triptych
7
Apakah ada versi produk kartesius yang tidak rangkap?
KJW
16
@ KJW Ya,set(cartesian product)
NoBugs
5
Seharusnya tidak ada duplikat dalam produk Cartesian, kecuali daftar input mengandung duplikat itu sendiri. Jika Anda tidak menginginkan duplikat dalam produk Cartesian, gunakan set(inputlist)semua daftar input Anda. Tidak pada hasilnya.
CamilB
@ Triptych apa? Definisi standar dari produk Cartesian adalah seperangkat. Mengapa begitu banyak orang yang merasa jengkel?
PascalIv

Jawaban:

378

itertools.product

Tersedia dari Python 2.6.

import itertools

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

Yang sama dengan,

for element in itertools.product([1, 2, 3], ['a', 'b'], [4, 5]):
    print(element)
Triptych
sumber
22
Hanya ingin menambahkan karakter '*' diperlukan jika Anda menggunakan variabel daftar panjang yang disediakan oleh OP.
brian buck
1
@ jaska: product()menghasilkan nitems_in_a_list ** nlistselemen dalam hasil ( reduce(mul, map(len, somelists))). Tidak ada alasan untuk percaya bahwa menghasilkan elemen tunggal tidak O(nlists)(diamortisasi) yaitu, kompleksitas waktu adalah sama seperti untuk bersarang for-loop sederhana misalnya, untuk input dalam pertanyaan :,nlists=3 jumlah total elemen dalam hasil :,3*2*2 dan setiap elemen memiliki nlistsitem ( 3dalam hal ini).
jfs
2
Apa gunanya *sebelum somelists? Apa fungsinya?
Vineet Kumar Doshi
6
@VineetKumarDoshi: Ini dia digunakan untuk membuka daftar ke beberapa argumen ke pemanggilan fungsi. Baca lebih lanjut di sini: stackoverflow.com/questions/36901/…
Moberg
4
Catatan: Ini hanya berfungsi jika setiap daftar mengandung setidaknya satu item
igo
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
sumber
38

Untuk Python 2.5 dan yang lebih lama:

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

Berikut ini adalah versi rekursif product()(hanya ilustrasi):

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

Contoh:

>>> 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
sumber
Versi rekursif tidak berfungsi jika beberapa di antaranya argsadalah iterator.
jfs
20

dengan itertools.product :

import itertools
result = list(itertools.product(*somelists))
SilentGhost
sumber
6
Apa gunanya *sebelum somelists?
Vineet Kumar Doshi
@VineetKumarDoshi "product (somelists)" adalah produk kartesius antara sublists dengan cara yang pertama kali Python mendapatkan "[1, 2, 3]" sebagai elemen dan kemudian mendapatkan elemen lain setelah comman berikutnya dan itu adalah linebreak jadi produk pertama istilah adalah ([1, 2, 3],), serupa untuk yang kedua ([4, 5],) dan seterusnya "[([1, 2, 3],), ([4, 5],), ( [6, 7],)] " . Jika Anda ingin mendapatkan produk cartesian antara elemen-elemen di dalam tuple, Anda perlu memberi tahu Python dengan Asterisk tentang struktur tuple. Untuk kamus, Anda menggunakan **. Lebih lanjut di sini .
hhh
19

Saya akan menggunakan daftar pemahaman:

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]]
pengguna1035648
sumber
1
Saya sangat suka solusi ini menggunakan daftar pemahaman. Saya tidak tahu mengapa tidak lebih dipilih, itu sangat sederhana.
llekn
20
@ lekn karena kode tersebut sepertinya sudah diperbaiki ke sejumlah daftar
Bằng Rikimaru
11

Ini adalah generator rekursif, yang tidak menyimpan daftar sementara

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

Keluaran:

[(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
sumber
1
Mereka disimpan di tumpukan.
Quentin Pradet
@ QuentinPradet maksud Anda generator seperti def f(): while True: yield 1akan terus meningkatkan ukuran tumpukan saat kita melewatinya?
Anurag Uniyal
@ QuentinPradet ya, tetapi bahkan dalam kasus ini hanya tumpukan yang diperlukan untuk kedalaman maksimal, bukan seluruh daftar, jadi dalam hal ini tumpukan 3
Anurag Uniyal
Itu benar, maaf. Benchmark bisa menarik. :)
Quentin Pradet
11

Dalam Python 2.6 dan di atas Anda dapat menggunakan 'itertools.product`. Dalam versi Python yang lebih lama Anda dapat menggunakan kode yang setara (hampir-lihat dokumentasi) berikut dari dokumentasi , setidaknya sebagai titik awal:

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)

Hasil dari keduanya adalah iterator, jadi jika Anda benar-benar membutuhkan daftar untuk diproses lebih lanjut, gunakan list(result).


sumber
Per dokumentasi, implementasi itertools.product sebenarnya TIDAK membangun hasil antara, yang bisa mahal. Menggunakan teknik ini bisa keluar dari tangan cukup cepat untuk daftar berukuran sedang.
Triptych
4
saya hanya bisa mengarahkan OP ke dokumentasi, bukan membacanya untuknya.
1
Kode dari dokumentasi dimaksudkan untuk menunjukkan apa fungsi fungsi produk, bukan sebagai solusi untuk versi Python sebelumnya.
Triptych
9

Meskipun sudah ada banyak jawaban, saya ingin membagikan beberapa pemikiran saya:

Pendekatan berulang

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

Pendekatan Rekursif

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]

Pendekatan Lambda

def cartesian_reduct(pools):
  return reduce(lambda x,y: product(x,y) , pools)
weiyixie
sumber
Dalam "Pendekatan Iteratif", mengapa hasil dideklarasikan sebagai result = [[]] Saya tahu itu list_of_list tetapi secara umum bahkan jika kita mendeklarasikan list_of_list, kita menggunakan [] dan bukan [[]]
Sachin S
Saya sedikit baru dalam hal solusi Pythonic. Apakah Anda atau orang yang lewat silakan menulis daftar pemahaman dalam "pendekatan berulang" dalam loop terpisah?
Johnny Boy
4

Pendekatan Rekursif:

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)

Pendekatan berulang:

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
sumber
3

Modifikasi kecil untuk solusi generator rekursif di atas dalam rasa variadic:

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

Dan tentu saja pembungkus yang membuatnya berfungsi sama persis dengan solusi itu:

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

dengan satu trade-off : itu memeriksa apakah rekursi harus pecah pada setiap loop luar, dan satu keuntungan : tidak ada hasil pada panggilan kosong, misalnya product(()), yang saya kira akan secara semantik lebih benar (lihat dokumen).

Mengenai pemahaman daftar: definisi matematika berlaku untuk sejumlah argumen arbitrer, sementara pemahaman daftar hanya bisa berurusan dengan jumlah yang diketahui dari mereka.

Mike Lu
sumber
2

Hanya untuk menambahkan sedikit pada apa yang telah dikatakan: jika Anda menggunakan sympy, Anda dapat menggunakan simbol daripada string yang membuatnya berguna secara matematis.

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

Tentang sympy .

Tyler Heers
sumber
1

Saya percaya ini bekerja:

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
sumber
0

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

keluaran:

[[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
sumber