Saya memiliki daftar dengan 15 angka, dan saya perlu menulis beberapa kode yang menghasilkan semua 32.768 kombinasi angka-angka itu.
Saya telah menemukan beberapa kode (oleh Googling) yang tampaknya melakukan apa yang saya cari, tetapi saya menemukan kode itu cukup buram dan saya khawatir menggunakannya. Ditambah lagi saya punya perasaan pasti ada solusi yang lebih elegan.
Satu-satunya hal yang terjadi pada saya adalah hanya loop melalui bilangan bulat desimal 1-32768 dan mengubahnya menjadi biner, dan menggunakan representasi biner sebagai filter untuk memilih angka yang sesuai.
Adakah yang tahu cara yang lebih baik? Menggunakan map()
, mungkin?
python
combinations
Ben
sumber
sumber
product
, dll.)Jawaban:
Lihatlah itertools.combinations :
Sejak 2.6, baterai disertakan!
sumber
list(itertools.combinations(iterable, r))
r
, yaitu kombinasi dari setiap panjang elemen berikutnya.Jawaban ini melewatkan satu aspek: OP meminta SEMUA kombinasi ... bukan hanya kombinasi panjang "r".
Jadi, Anda harus mengulang semua "L":
Atau - jika Anda ingin mendapatkan manis (atau menekuk otak siapa pun yang membaca kode Anda setelah Anda) - Anda dapat menghasilkan rantai generator "kombinasi ()", dan beralih melalui itu:
sumber
powerset()
generator di bagian resepitertools
dokumentasi lebih sederhana, berpotensi menggunakan lebih sedikit memori, dan kemungkinan lebih cepat daripada implementasi yang ditunjukkan di sini.itertools.combinations
mempertahankan pesanan barang dalam daftar yang dihasilkannya. Jadi, jika input diurutkan secara leksikal, maka masing-masing output juga akan.itertools.combinations
menghasilkan kombinasi k di antara n dalam urutan leksikografis, tetapi tidak semua kombinasi hingga k di antara n.powerset
menghasilkan semua kombinasi hingga k, tetapi tidak dalam urutan leksikografis sejauh yang saya mengerti: powerset ([1,2]) -> [(), (1,), (2,), (1, 2)] . Bukankah seharusnya: [(), (1,), (1, 2), (2,)]?Ini adalah one-liner yang malas, juga menggunakan itertools:
Gagasan utama di balik jawaban ini: ada 2 ^ N kombinasi - sama dengan jumlah string biner panjang N. Untuk setiap string biner, Anda memilih semua elemen yang sesuai dengan "1".
Hal yang perlu dipertimbangkan:
len(...)
diitems
(solusi: jikaitems
sesuatu seperti iterable seperti generator, mengubahnya menjadi daftar pertama denganitems=list(_itemsArg)
)items
tidak acak (solusi: jangan gila){2,2,1}
dan{2,1,1}
keduanya akan runtuh ke{2,1}
(solusi: gunakancollections.Counter
sebagai pengganti drop-in untukset
; itu pada dasarnya adalah multiset ... meskipun Anda mungkin perlu menggunakan nantituple(sorted(Counter(...).elements()))
jika Anda membutuhkannya dapat hashable)Demo
sumber
Dalam komentar di bawah jawaban yang sangat terangkat oleh @Dan H, disebutkan dibuat
powerset()
resep dalamitertools
dokumentasi — termasuk satu oleh Dan sendiri . Namun , sejauh ini belum ada yang mempostingnya sebagai jawaban. Karena itu mungkin salah satu yang lebih baik jika bukan pendekatan terbaik untuk masalah itu — dan diberi sedikit dorongan dari komentator lain, itu ditunjukkan di bawah ini. Fungsi menghasilkan semua kombinasi unik dari elemen daftar dari setiap panjang yang mungkin (termasuk yang mengandung nol dan semua elemen).Catatan : Jika, agak berbeda, tujuannya adalah untuk mendapatkan hanya kombinasi dari unsur-unsur yang unik, mengubah baris
s = list(iterable)
untuks = list(set(iterable))
untuk menghilangkan elemen duplikat. Terlepas dari itu, fakta bahwa padaiterable
akhirnya diubah menjadilist
sarana itu akan bekerja dengan generator (tidak seperti beberapa jawaban lainnya).Keluaran:
sumber
list()
konversi itu?Inilah salah satu yang menggunakan rekursi:
sumber
new_data = copy.copy(data)
- baris ini berlebihan sejauh yang saya lihat, tidak mempengaruhi apa punSatu garis ini memberi Anda semua kombinasi (antara
0
dann
item jika daftar / set asli berisin
elemen yang berbeda) dan menggunakan metode asliitertools.combinations
:Python 2
Python 3
Outputnya adalah:
Cobalah online:
http://ideone.com/COghfX
sumber
['b', 'a']
.TypeError: can only concatenate list (not "map") to list
Saya setuju dengan Dan H bahwa Ben memang meminta semua kombinasi.
itertools.combinations()
tidak memberikan semua kombinasi.Masalah lain adalah, jika input iterable besar, mungkin lebih baik mengembalikan generator daripada semua yang ada di daftar:
sumber
Ini adalah pendekatan yang dapat dengan mudah ditransfer ke semua bahasa pemrograman yang mendukung rekursi (tanpa itertools, tanpa hasil, tanpa pemahaman daftar) :
sumber
Anda dapat membuat semua kombinasi daftar dalam python menggunakan kode sederhana ini
Hasilnya adalah:
sumber
Saya pikir saya akan menambahkan fungsi ini untuk mereka yang mencari jawaban tanpa mengimpor itertools atau perpustakaan tambahan lainnya.
Penggunaan Generator Hasil Sederhana:
Output dari Contoh penggunaan di atas:
sumber
Berikut ini adalah solusi lain (satu-liner), yang melibatkan penggunaan
itertools.combinations
fungsi, tetapi di sini kami menggunakan pemahaman daftar ganda (sebagai lawan dari for for loop atau sum):Demo:
sumber
keluaran
sumber
Di bawah ini adalah "jawaban rekursif standar", mirip dengan jawaban serupa lainnya https://stackoverflow.com/a/23743696/711085 . (Kami tidak perlu khawatir kehabisan ruang stack secara realistis karena tidak mungkin kami bisa memproses semua permutasi N!)
Ia mengunjungi setiap elemen secara bergantian, dan mengambil atau membiarkannya (kita dapat langsung melihat kardinalitas 2 ^ N dari algoritma ini).
Demo:
sumber
Menggunakan pemahaman daftar:
Outputnya adalah:
sumber
Kode ini menggunakan algoritma sederhana dengan daftar bersarang ...
sumber
""
).Saya tahu jauh lebih praktis untuk menggunakan itertools untuk mendapatkan semua kombinasi, tetapi Anda dapat mencapai hal ini sebagian dengan hanya memahami daftar jika Anda memang menginginkannya, asalkan Anda ingin banyak kode.
Untuk kombinasi dua pasang:
Dan, untuk kombinasi tiga pasang, semudah ini:
Hasilnya identik dengan menggunakan itertools.combinations:
sumber
Tanpa menggunakan itertools:
sumber
Berikut adalah dua implementasi dari
itertools.combinations
Salah satu yang mengembalikan daftar
Satu mengembalikan generator
Harap dicatat bahwa memberikan fungsi pembantu kepada mereka disarankan karena argumen sebelumnya adalah statis dan tidak berubah dengan setiap panggilan
Ini adalah kasus yang sangat dangkal tetapi lebih baik aman daripada menyesal
sumber
Bagaimana dengan ini .. menggunakan string bukan daftar, tetapi hal yang sama .. string dapat diperlakukan seperti daftar di Python:
sumber
Kombinasi dari itertools
Terima kasih
sumber
Tanpa
itertools
Python 3 Anda bisa melakukan sesuatu seperti ini:dimana awalnya
carry = "".
sumber
3 fungsi:
sumber
Ini implementasi saya
sumber
Anda juga dapat menggunakan fungsi powerset dari
more_itertools
paket luar biasa .Kami juga dapat memverifikasi, bahwa memenuhi persyaratan OP
sumber
sumber
Jika seseorang mencari daftar terbalik, seperti saya:
sumber
sumber