kombinasi antara dua daftar?

187

Sudah lama dan saya mengalami kesulitan membungkus kepala saya di sekitar algoritma yang saya coba buat. Pada dasarnya, saya memiliki dua daftar dan ingin mendapatkan semua kombinasi dari dua daftar.

Saya mungkin tidak menjelaskannya dengan benar, jadi inilah contohnya.

name = 'a', 'b'
number = 1, 2

output dalam hal ini adalah:

1.  A1 B2
2.  B1 A2

Bagian yang sulit adalah saya mungkin memiliki lebih banyak item dalam variabel "nama" daripada item dalam variabel "angka" (angka akan selalu sama dengan atau kurang dari variabel nama).

Saya bingung bagaimana melakukan semua kombinasi (bersarang untuk loop?) Dan bahkan lebih bingung pada logika untuk menggeser item dalam variabel nama jika ada lebih banyak item dalam nama daripada mereka dalam daftar nomor.

Saya bukan programmer terbaik tetapi saya pikir saya bisa mencobanya jika seseorang dapat membantu saya memperjelas logika / algoriythm untuk mencapai ini. Jadi saya baru saja terjebak di sarang untuk loop.

Memperbarui:

Inilah output dengan 3 variabel dan 2 angka:

name = 'a', 'b', 'c'
number = 1, 2

keluaran:

1.  A1 B2
2.  B1 A2
3.  A1 C2
4.  C1 A2
5.  B1 C2
6.  C1 B2
pengguna1735075
sumber
1
@ dm03514 Saya melihat itu, dan menemukan contoh untuk tujuan yang agak mirip menggunakan itertools tapi saya membuat prototipe dengan python tetapi akan menulis kode terakhir dalam bahasa lain jadi saya tidak ingin menggunakan alat apa pun yang tidak tersedia di tempat lain.
user1735075
1
Apa yang Anda minta tidak terlalu masuk akal. Jika daftar pertama berisi A, B, C dan yang kedua berisi 1,2, hasil apa yang Anda harapkan? Ini dapat dilakukan jika contoh yang Anda berikan masing-masing memiliki 4 hasil berbeda dari satu huruf dan satu angka (A1, A2, B1, B2), atau jika kedua daftar harus memiliki ukuran yang sama.
interjay
1
Saya setuju dengan interjay. Silakan tentukan hasil dalam case ukuran tidak sama, kalau tidak, tidak mungkin untuk memberikan solusi umum.
Bakuriu
Hai Semua orang, saya memperbarui jawaban untuk menunjukkan output dengan 3 nama dan 2 angka .. Saya pikir saya menjelaskannya dengan baik, tidak yakin mengapa downvote.
user1735075

Jawaban:

93

Catatan : Jawaban ini untuk pertanyaan spesifik yang diajukan di atas. Jika Anda di sini dari Google dan hanya mencari cara untuk mendapatkan produk Cartesian dengan Python, itertools.productatau pemahaman daftar sederhana mungkin apa yang Anda cari - lihat jawaban lainnya.


Misalkan len(list1) >= len(list2). Maka yang Anda inginkan adalah mengambil semua permutasi len(list2)dari list1dan mencocokkannya dengan item dari list2. Dengan python:

import itertools
list1=['a','b','c']
list2=[1,2]

[list(zip(x,list2)) for x in itertools.permutations(list1,len(list2))]

Kembali

[[('a', 1), ('b', 2)], [('a', 1), ('c', 2)], [('b', 1), ('a', 2)], [('b', 1), ('c', 2)], [('c', 1), ('a', 2)], [('c', 1), ('b', 2)]]
interjay
sumber
1
Hasilnya persis seperti yang saya inginkan, tetapi mungkinkah untuk berbagi logika di balik cara melakukannya? Jika saya mengonversi kode saya ke C atau Java, saya tidak akan memiliki akses ke zip atau itertools (meskipun mereka membuat hidup sangat sangat mudah)
user1735075
3
@ user1735075 Lihatlah dokumentasi
sloth
1
@ user1735075: apakah Anda tahu bahwa python adalah open source? Jadi Anda bisa mengunduh sumbernya dan melihat apa yang mereka lakukan. +1 kepada Tn. Steak untuk menunjukkan bahwa dokumentasi sebenarnya memiliki contoh implementasi yang tidak digunakan zipdan serupa.
Bakuriu
2
saya benar-benar tidak bisa mendapatkan ini berfungsi, bahkan dengan contoh Anda ... semua saya dapatkan adalah daftar objek zip ..: |
m1nkeh
1
@logic memberikan solusi yang seharusnya diterima.
Bernhard Wagner
502

Cara paling sederhana adalah dengan menggunakan itertools.product:

a = ["foo", "melon"]
b = [True, False]
c = list(itertools.product(a, b))
>> [("foo", True), ("foo", False), ("melon", True), ("melon", False)]
DrIDK
sumber
11
OP tidak meminta produk Cartesian, dan jawaban ini (serta sebagian besar yang lain) tidak memberikan hasil yang diharapkan yang ditentukan dalam pertanyaan.
interjay
17
@ interjay Anda sangat benar tetapi karena terlalu banyak orang tampaknya menemukan jawaban ini benar maka saya hanya dapat berasumsi bahwa judul pertanyaan kurang konteks.
xpy
3
@xpy Judul terlalu pendek untuk menjelaskan semuanya. Itu sebabnya Anda perlu membaca pertanyaan yang sebenarnya.
interjay
10
OP menginginkan izin, tetapi Google mengirim siapa pun yang mencari kombinasi (seperti saya) untuk jawaban ini - senang melihatnya mendapat 8 kali suara!
Josh Friedlander
160

Mungkin lebih sederhana daripada yang paling sederhana di atas:

>>> a = ["foo", "bar"]
>>> b = [1, 2, 3]
>>> [(x,y) for x in a for y in b]  # for a list
[('foo', 1), ('foo', 2), ('foo', 3), ('bar', 1), ('bar', 2), ('bar', 3)]
>>> ((x,y) for x in a for y in b)  # for a generator if you worry about memory or time complexity.
<generator object <genexpr> at 0x1048de850>

tanpa impor

logika
sumber
Solusi terbaik! Terima kasih! Solusi lain salah atau hanya berfungsi dalam kasus tertentu seperti a> b dll.
Philipp Schwarz
3
Sebagian besar solusi Pythonic! (dan menghindari impor yang tidak perlu)
Dalker
6
Kompleksitas waktu adalah O (n ^ 2)
Deepak Sharma
2
Solusi taruhan !! Dasar-dasar kosong adalah cara terbaik selalu
Sabyasachi
22

Saya mencari daftar yang dikalikan dengan dirinya sendiri dengan hanya kombinasi unik, yang disediakan sebagai fungsi ini.

import itertools
itertools.combinations(list, n_times)

Di sini sebagai kutipan dari dokumen Python pada itertools Itu mungkin membantu Anda menemukan apa yang Anda cari.

Combinatoric generators:

Iterator                                 | Results
-----------------------------------------+----------------------------------------
product(p, q, ... [repeat=1])            | cartesian product, equivalent to a 
                                         |   nested for-loop
-----------------------------------------+----------------------------------------
permutations(p[, r])                     | r-length tuples, all possible 
                                         |   orderings, no repeated elements
-----------------------------------------+----------------------------------------
combinations(p, r)                       | r-length tuples, in sorted order, no 
                                         |   repeated elements
-----------------------------------------+----------------------------------------
combinations_with_replacement(p, r)      | r-length tuples, in sorted order, 
                                         | with repeated elements
-----------------------------------------+----------------------------------------
product('ABCD', repeat=2)                | AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations('ABCD', 2)                  | AB AC AD BA BC BD CA CB CD DA DB DC
combinations('ABCD', 2)                  | AB AC AD BC BD CD
combinations_with_replacement('ABCD', 2) | AA AB AC AD BB BC BD CC CD DD
ThorSummoner
sumber
11

Anda mungkin ingin mencoba pemahaman daftar satu baris:

>>> [name+number for name in 'ab' for number in '12']
['a1', 'a2', 'b1', 'b2']
>>> [name+number for name in 'abc' for number in '12']
['a1', 'a2', 'b1', 'b2', 'c1', 'c2']
Idanmel
sumber
11

cara terbaik untuk mengetahui semua kombinasi untuk sejumlah besar daftar adalah:

import itertools
from pprint import pprint

inputdata = [
    ['a', 'b', 'c'],
    ['d'],
    ['e', 'f'],
]
result = list(itertools.product(*inputdata))
pprint(result)

hasilnya adalah:

[('a', 'd', 'e'),
 ('a', 'd', 'f'),
 ('b', 'd', 'e'),
 ('b', 'd', 'f'),
 ('c', 'd', 'e'),
 ('c', 'd', 'f')]
Ishan Rastogi
sumber
Terima kasih, jawaban yang bagus!
toinbis
10

Atau jawaban KISS untuk daftar pendek:

[(i, j) for i in list1 for j in list2]

Tidak sebagus itertools tetapi Anda menggunakan python sehingga kinerja sudah bukan perhatian utama Anda ...

Saya suka semua jawaban lain juga!

Fletch F Fletch
sumber
8

perbaikan kecil untuk jawaban dari interjay, untuk menjadikan hasilnya sebagai daftar rata.

>>> list3 = [zip(x,list2) for x in itertools.permutations(list1,len(list2))]
>>> import itertools
>>> chain = itertools.chain(*list3)
>>> list4 = list(chain)
[('a', 1), ('b', 2), ('a', 1), ('c', 2), ('b', 1), ('a', 2), ('b', 1), ('c', 2), ('c', 1), ('a', 2), ('c', 1), ('b', 2)]

referensi dari tautan ini

Zhou Mass
sumber
4

Tanpa itertools

[(list1[i], list2[j]) for i in xrange(len(list1)) for j in xrange(len(list2))]
pengguna3684792
sumber
4

Menjawab pertanyaan "diberikan dua daftar, temukan semua kemungkinan permutasi berpasangan dari satu item dari setiap daftar" dan menggunakan fungsionalitas Python dasar (yaitu, tanpa itertools) dan, karenanya, membuatnya mudah untuk direplikasi untuk bahasa pemrograman lain:

def rec(a, b, ll, size):
    ret = []
    for i,e in enumerate(a):
        for j,f in enumerate(b):
            l = [e+f]
            new_l = rec(a[i+1:], b[:j]+b[j+1:], ll, size)
            if not new_l:
                ret.append(l)
            for k in new_l:
                l_k = l + k
                ret.append(l_k)
                if len(l_k) == size:
                    ll.append(l_k)
    return ret

a = ['a','b','c']
b = ['1','2']
ll = []
rec(a,b,ll, min(len(a),len(b)))
print(ll)

Kembali

[['a1', 'b2'], ['a1', 'c2'], ['a2', 'b1'], ['a2', 'c1'], ['b1', 'c2'], ['b2', 'c1']]
komputeris
sumber
2

Jawaban yang lebih baik untuk ini hanya berfungsi untuk panjang daftar tertentu yang disediakan.

Berikut adalah versi yang berfungsi untuk setiap input yang panjang. Ini juga membuat algoritma jelas dalam hal konsep matematika kombinasi dan permutasi.

from itertools import combinations, permutations
list1 = ['1', '2']
list2 = ['A', 'B', 'C']

num_elements = min(len(list1), len(list2))
list1_combs = list(combinations(list1, num_elements))
list2_perms = list(permutations(list2, num_elements))
result = [
  tuple(zip(perm, comb))
  for comb in list1_combs
  for perm in list2_perms
]

for idx, ((l11, l12), (l21, l22)) in enumerate(result):
  print(f'{idx}: {l11}{l12} {l21}{l22}')

Output ini:

0: A1 B2
1: A1 C2
2: B1 A2
3: B1 C2
4: C1 A2
5: C1 B2
Steve Alexander
sumber