Bagaimana cara mendapatkan semua kemungkinan kombinasi elemen daftar?

423

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?

Ben
sumber
9
Pembaca harus mencatat bahwa apakah item daftar itu unik atau tidak merupakan pertimbangan yang sangat penting, karena banyak algoritma kemudian akan menghitung lebih dari beberapa subset (mis. 'Abccc' -> ['', 'a', 'b', 'c', 'c' , 'c', 'ac', 'ac', 'ac', ...]. Solusi yang mudah adalah dengan mendorong semua elemen dalam satu set sebelum mendapatkan permutasi mereka
ninjagecko
@ninjagecko Menggunakan perpustakaan Set tidak efisien karena masing-masing adalah O (n) yang terbaik. Jadi menambahkan fungsi n ke set sebenarnya O (n ^ 2)!
Scott Biggs
Dari membaca pertanyaan dengan cermat, tampaknya OP meminta PowerSet dari daftar 15 angka, tidak semua kombinasi. Saya pikir ini mungkin mengapa jawabannya ada di mana-mana.
Scott Biggs
@Scott Biggs: apakah Anda yakin tentang Python di sini? Mengatur penyisipan dan pencarian adalah O (1) case rata-rata Mereka seperti kamus. Mereka menggunakan hashing. Python tidak memiliki perpustakaan set khusus (ada di perpustakaan standar). Kami memasukkan angka di sini bukan fungsi. (Akan tetap tidak efisien untuk menggunakan memori O (2 ^ n); solusi yang tepat untuk orang-orang yang menginginkan kombinasi daripada powerset adalah implementasi rekursif yang sederhana, atau product, dll.)
ninjagecko

Jawaban:

467

Lihatlah itertools.combinations :

itertools.combinations(iterable, r)

Kembalikan r panjang berikutnya elemen dari input iterable.

Kombinasi dipancarkan dalam urutan leksikografis. Jadi, jika input iterable diurutkan, kombinasi tuple akan diproduksi dalam urutan.

Sejak 2.6, baterai disertakan!

James Brady
sumber
31
Anda bisa daftar semuanya. list(itertools.combinations(iterable, r))
silgon
1
apakah ada sesuatu yang tidak memerlukan r, yaitu kombinasi dari setiap panjang elemen berikutnya.
mLstudent33
630

Jawaban ini melewatkan satu aspek: OP meminta SEMUA kombinasi ... bukan hanya kombinasi panjang "r".

Jadi, Anda harus mengulang semua "L":

import itertools

stuff = [1, 2, 3]
for L in range(0, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        print(subset)

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:

from itertools import chain, combinations
def all_subsets(ss):
    return chain(*map(lambda x: combinations(ss, x), range(0, len(ss)+1)))

for subset in all_subsets(stuff):
    print(subset)
Dan H
sumber
42
Terima kasih atas dukungannya! Dalam minggu-minggu sejak saya memposting balasan di atas, saya telah menemukan bahwa NAMA konsep untuk apa yang dicari Ben adalah "powerset" dari set 15 item asli. Bahkan, contoh implementasi diberikan pada halaman standar python "itertools" doc: docs.python.org/library/itertools.html (grep untuk "powerset").
Dan H
38
Bagi siapa pun yang membaca sejauh ini: Fungsi powerset()generator di bagian resep itertoolsdokumentasi lebih sederhana, berpotensi menggunakan lebih sedikit memori, dan kemungkinan lebih cepat daripada implementasi yang ditunjukkan di sini.
martineau
Apakah mungkin untuk menghasilkan semua kombinasi dalam urutan leksikografis?
guik
@guik: Saya 99% yakin bahwa itertools.combinationsmempertahankan pesanan barang dalam daftar yang dihasilkannya. Jadi, jika input diurutkan secara leksikal, maka masing-masing output juga akan.
Dan H
Ya, itertools.combinationsmenghasilkan kombinasi k di antara n dalam urutan leksikografis, tetapi tidak semua kombinasi hingga k di antara n. powersetmenghasilkan 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,)]?
guik
52

Ini adalah one-liner yang malas, juga menggunakan itertools:

from itertools import compress, product

def combinations(items):
    return ( set(compress(items,mask)) for mask in product(*[[0,1]]*len(items)) )
    # alternative:                      ...in product([0,1], repeat=len(items)) )

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".

items=abc * mask=###
 |
 V
000 -> 
001 ->   c
010 ->  b
011 ->  bc
100 -> a
101 -> a c
110 -> ab
111 -> abc

Hal yang perlu dipertimbangkan:

  • Hal ini mengharuskan Anda dapat menghubungi len(...)di items(solusi: jika itemssesuatu seperti iterable seperti generator, mengubahnya menjadi daftar pertama dengan items=list(_itemsArg))
  • Ini mensyaratkan bahwa urutan iterasi aktif itemstidak acak (solusi: jangan gila)
  • Ini mensyaratkan bahwa item itu unik, atau yang lain {2,2,1}dan {2,1,1}keduanya akan runtuh ke {2,1}(solusi: gunakan collections.Countersebagai pengganti drop-in untuk set; itu pada dasarnya adalah multiset ... meskipun Anda mungkin perlu menggunakan nanti tuple(sorted(Counter(...).elements()))jika Anda membutuhkannya dapat hashable)

Demo

>>> list(combinations(range(4)))
[set(), {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}, {0}, {0, 3}, {0, 2}, {0, 2, 3}, {0, 1}, {0, 1, 3}, {0, 1, 2}, {0, 1, 2, 3}]

>>> list(combinations('abcd'))
[set(), {'d'}, {'c'}, {'c', 'd'}, {'b'}, {'b', 'd'}, {'c', 'b'}, {'c', 'b', 'd'}, {'a'}, {'a', 'd'}, {'a', 'c'}, {'a', 'c', 'd'}, {'a', 'b'}, {'a', 'b', 'd'}, {'a', 'c', 'b'}, {'a', 'c', 'b', 'd'}]
ninjagecko
sumber
46

Dalam komentar di bawah jawaban yang sangat terangkat oleh @Dan H, disebutkan dibuat powerset()resep dalam itertoolsdokumentasi — 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)untuk s = list(set(iterable))untuk menghilangkan elemen duplikat. Terlepas dari itu, fakta bahwa pada iterableakhirnya diubah menjadi listsarana itu akan bekerja dengan generator (tidak seperti beberapa jawaban lainnya).

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)  # allows duplicate elements
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

stuff = [1, 2, 3]
for i, combo in enumerate(powerset(stuff), 1):
    print('combo #{}: {}'.format(i, combo))

Keluaran:

combo #1: ()
combo #2: (1,)
combo #3: (2,)
combo #4: (3,)
combo #5: (1, 2)
combo #6: (1, 3)
combo #7: (2, 3)
combo #8: (1, 2, 3)
martineau
sumber
Untuk apa list()konversi itu?
AMC
@Alexander: Untuk memungkinkan panjang iterable ditentukan.
martineau
36

Inilah salah satu yang menggunakan rekursi:

>>> import copy
>>> def combinations(target,data):
...     for i in range(len(data)):
...         new_target = copy.copy(target)
...         new_data = copy.copy(data)
...         new_target.append(data[i])
...         new_data = data[i+1:]
...         print new_target
...         combinations(new_target,
...                      new_data)
...                      
... 
>>> target = []
>>> data = ['a','b','c','d']
>>> 
>>> combinations(target,data)
['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['a', 'b', 'd']
['a', 'c']
['a', 'c', 'd']
['a', 'd']
['b']
['b', 'c']
['b', 'c', 'd']
['b', 'd']
['c']
['c', 'd']
['d']
darxtrix
sumber
Apakah ini dapat diubah untuk mengembalikan daftar daftar alih-alih mencetak?
James Vickery
@JamesVickery ya, Anda bisa melihat membuat daftar di luar fungsi dan menambahkannya, atau (lebih baik) menjadikan fungsi sebagai generator, lihat kata kunci 'hasil' :)
Dangercrow
new_data = copy.copy(data)- baris ini berlebihan sejauh yang saya lihat, tidak mempengaruhi apa pun
Dmitriy Fialkovskiy
31

Satu garis ini memberi Anda semua kombinasi (antara 0dan nitem jika daftar / set asli berisi nelemen yang berbeda) dan menggunakan metode asli itertools.combinations:

Python 2

from itertools import combinations

input = ['a', 'b', 'c', 'd']

output = sum([map(list, combinations(input, i)) for i in range(len(input) + 1)], [])

Python 3

from itertools import combinations

input = ['a', 'b', 'c', 'd']

output = sum([list(map(list, combinations(input, i))) for i in range(len(input) + 1)], [])

Outputnya adalah:

[[],
 ['a'],
 ['b'],
 ['c'],
 ['d'],
 ['a', 'b'],
 ['a', 'c'],
 ['a', 'd'],
 ['b', 'c'],
 ['b', 'd'],
 ['c', 'd'],
 ['a', 'b', 'c'],
 ['a', 'b', 'd'],
 ['a', 'c', 'd'],
 ['b', 'c', 'd'],
 ['a', 'b', 'c', 'd']]

Cobalah online:

http://ideone.com/COghfX

Mathieu Rodic
sumber
Ini adalah permutasi
AdHominem
15
@ AdHominem: tidak, tidak. Ini daftar semua kombinasi. Permutasi akan mencakup, misalnya ['b', 'a'].
naught101
TypeError: can only concatenate list (not "map") to list
0x48piraj
@ 0x48piraj: terima kasih atas perhatiannya, saya mengedit jawaban saya karenanya!
Mathieu Rodic
21

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:

iterable = range(10)
for s in xrange(len(iterable)+1):
  for comb in itertools.combinations(iterable, s):
    yield comb
HongboZhu
sumber
1
Contoh yang bagus. Saya suka generator ... dan saya suka Python karena memilikinya! Contoh ini hanya memiliki satu kombinasi () objek di sekitar pada suatu waktu, dan menghasilkan salah satu kombinasi pada suatu waktu. (Mungkin Anda ingin menambahkan blok def sekitar ini - sebagai contoh penggunaan.) Perhatikan bahwa implementasi saya (dengan rantai (), yang diberikan di atas) tidak terlalu jauh lebih buruk: memang benar yang membuat semua generator len (iterable) di sekali ... tetapi TIDAK membuat semua 2 ** len (iterable) kombinasi sekaligus, seperti - untuk pemahaman saya - rantai "menggunakan" generator pertama sebelum menggambar dari yang berikutnya.
Dan H
18

Ini adalah pendekatan yang dapat dengan mudah ditransfer ke semua bahasa pemrograman yang mendukung rekursi (tanpa itertools, tanpa hasil, tanpa pemahaman daftar) :

def combs(a):
    if len(a) == 0:
        return [[]]
    cs = []
    for c in combs(a[1:]):
        cs += [c, c+[a[0]]]
    return cs

>>> combs([1,2,3,4,5])
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], ..., [5, 4, 3, 2, 1]]
Jonathan R
sumber
Ah! Implementasi yang bagus. Saya mengenali HEAD = a [0], TAIL = a [1:] dari Prolog. Atau mobil = a [0], cdr = a [1:] dari Lisp. Saya ingin tahu apakah kita bisa menggunakan memoisasi di sini ...
Javier Ruiz
Benar. Mengiris daftar adalah O (k) di mana k adalah panjang irisan. Saya kira orang bisa mempercepat ini dengan melakukan pencarian di peta yang akan membuatnya O (1) di semua berjalan kecuali yang pertama. Perhatikan bahwa implementasi ini tidak boleh dijadikan rujukan untuk kinerja. Untuk itu ada implementasi yang lebih baik. Implementasi ini hanya untuk kesederhanaan dan portabilitas untuk sebagian besar bahasa lainnya.
Jonathan R
14

Anda dapat membuat semua kombinasi daftar dalam python menggunakan kode sederhana ini

import itertools

a = [1,2,3,4]
for i in xrange(0,len(a)+1):
   print list(itertools.combinations(a,i))

Hasilnya adalah:

[()]
[(1,), (2,), (3,), (4,)]
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]
[(1, 2, 3, 4)]
saimadhu.polamuri
sumber
Bug dalam kode ini: tidak mengembalikan set kosong. Mungkin berarti xrange (0, ...) tetapi belum diuji. sunting : Saya melanjutkan dan mengedit jawaban Anda untuk memperbaikinya.
ninjagecko
13

Saya pikir saya akan menambahkan fungsi ini untuk mereka yang mencari jawaban tanpa mengimpor itertools atau perpustakaan tambahan lainnya.

def powerSet(items):
    """
    Power set generator: get all possible combinations of a list’s elements

    Input:
        items is a list
    Output:
        returns 2**n combination lists one at a time using a generator 

    Reference: edx.org 6.00.2x Lecture 2 - Decision Trees and dynamic programming
    """

    N = len(items)
    # enumerate the 2**N possible combinations
    for i in range(2**N):
        combo = []
        for j in range(N):
            # test bit jth of integer i
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        yield combo

Penggunaan Generator Hasil Sederhana:

for i in powerSet([1,2,3,4]):
    print (i, ", ",  end="")

Output dari Contoh penggunaan di atas:

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


sumber
Saya pikir ini solusi yang sangat rapi.
greentec
8

Berikut ini adalah solusi lain (satu-liner), yang melibatkan penggunaan itertools.combinationsfungsi, tetapi di sini kami menggunakan pemahaman daftar ganda (sebagai lawan dari for for loop atau sum):

def combs(x):
    return [c for i in range(len(x)+1) for c in combinations(x,i)]

Demo:

>>> combs([1,2,3,4])
[(), 
 (1,), (2,), (3,), (4,), 
 (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), 
 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), 
 (1, 2, 3, 4)]
ninjagecko
sumber
5
from itertools import permutations, combinations


features = ['A', 'B', 'C']
tmp = []
for i in range(len(features)):
    oc = combinations(features, i + 1)
    for c in oc:
        tmp.append(list(c))

keluaran

[
 ['A'],
 ['B'],
 ['C'],
 ['A', 'B'],
 ['A', 'C'],
 ['B', 'C'],
 ['A', 'B', 'C']
]
Andrew Li
sumber
4

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

def combs(xs, i=0):
    if i==len(xs):
        yield ()
        return
    for c in combs(xs,i+1):
        yield c
        yield c+(xs[i],)

Demo:

>>> list( combs(range(5)) )
[(), (0,), (1,), (1, 0), (2,), (2, 0), (2, 1), (2, 1, 0), (3,), (3, 0), (3, 1), (3, 1, 0), (3, 2), (3, 2, 0), (3, 2, 1), (3, 2, 1, 0), (4,), (4, 0), (4, 1), (4, 1, 0), (4, 2), (4, 2, 0), (4, 2, 1), (4, 2, 1, 0), (4, 3), (4, 3, 0), (4, 3, 1), (4, 3, 1, 0), (4, 3, 2), (4, 3, 2, 0), (4, 3, 2, 1), (4, 3, 2, 1, 0)]

>>> list(sorted( combs(range(5)), key=len))
[(), 
 (0,), (1,), (2,), (3,), (4,), 
 (1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3), 
 (2, 1, 0), (3, 1, 0), (3, 2, 0), (3, 2, 1), (4, 1, 0), (4, 2, 0), (4, 2, 1), (4, 3, 0), (4, 3, 1), (4, 3, 2), 
 (3, 2, 1, 0), (4, 2, 1, 0), (4, 3, 1, 0), (4, 3, 2, 0), (4, 3, 2, 1), 
 (4, 3, 2, 1, 0)]

>>> len(set(combs(range(5))))
32
ninjagecko
sumber
2

Menggunakan pemahaman daftar:

def selfCombine( list2Combine, length ):
    listCombined = str( ['list2Combine[i' + str( i ) + ']' for i in range( length )] ).replace( "'", '' ) \
                     + 'for i0 in range(len( list2Combine ) )'
    if length > 1:
        listCombined += str( [' for i' + str( i ) + ' in range( i' + str( i - 1 ) + ', len( list2Combine ) )' for i in range( 1, length )] )\
            .replace( "', '", ' ' )\
            .replace( "['", '' )\
            .replace( "']", '' )

    listCombined = '[' + listCombined + ']'
    listCombined = eval( listCombined )

    return listCombined

list2Combine = ['A', 'B', 'C']
listCombined = selfCombine( list2Combine, 2 )

Outputnya adalah:

['A', 'A']
['A', 'B']
['A', 'C']
['B', 'B']
['B', 'C']
['C', 'C']
zmk
sumber
4
Proposal ini untuk melakukan string mangling untuk membangun set?!?! Gagak suci .... Dan: itu bukan mengembalikan powerset, melainkan sesuatu seperti kombinasi_with_lokasi (). (Lihat docs.python.org/library/… )
Dan H
Ini memang melakukan hal yang sama dengan kombinasi_with_lokasi () , tetapi setidaknya pada kotak saya ini berjalan sedikit lebih cepat daripada itertools . Apa yang bisa saya katakan, saya suka daftar pemahaman.
zmk
1
Terima kasih atas jawabannya! Bagaimana dengan membuat listCombined dengan daftar terbalik seperti ['A', 'A'], ['A', 'B'], ['A', 'C'], ['B', 'A'], [ 'B', 'B'], ['B', 'C'], ['C', 'A'], ['C', 'B'] dan ['C', 'C'] yang mencakup segala sesuatu?
Karyo
Sangat menarik, tetapi python saya tidak cukup memahami seluk-beluk di sini. Apakah ada sesuatu yang istimewa tentang penggunaan listCombined dalam lingkup yang berbeda dan fakta bahwa for loop semuanya dalam satu baris? Saya mencoba untuk port ini ke Jawa dengan sedikit keberuntungan.
Scott Biggs
2

Kode ini menggunakan algoritma sederhana dengan daftar bersarang ...

# FUNCTION getCombos: To generate all combos of an input list, consider the following sets of nested lists...
#
#           [ [ [] ] ]
#           [ [ [] ], [ [A] ] ]
#           [ [ [] ], [ [A],[B] ],         [ [A,B] ] ]
#           [ [ [] ], [ [A],[B],[C] ],     [ [A,B],[A,C],[B,C] ],                   [ [A,B,C] ] ]
#           [ [ [] ], [ [A],[B],[C],[D] ], [ [A,B],[A,C],[B,C],[A,D],[B,D],[C,D] ], [ [A,B,C],[A,B,D],[A,C,D],[B,C,D] ], [ [A,B,C,D] ] ]
#
#  There is a set of lists for each number of items that will occur in a combo (including an empty set).
#  For each additional item, begin at the back of the list by adding an empty list, then taking the set of
#  lists in the previous column (e.g., in the last list, for sets of 3 items you take the existing set of
#  3-item lists and append to it additional lists created by appending the item (4) to the lists in the
#  next smallest item count set. In this case, for the three sets of 2-items in the previous list. Repeat
#  for each set of lists back to the initial list containing just the empty list.
#

def getCombos(listIn = ['A','B','C','D','E','F'] ):
    listCombos = [ [ [] ] ]     # list of lists of combos, seeded with a list containing only the empty list
    listSimple = []             # list to contain the final returned list of items (e.g., characters)

    for item in listIn:
        listCombos.append([])   # append an emtpy list to the end for each new item added
        for index in xrange(len(listCombos)-1, 0, -1):  # set the index range to work through the list
            for listPrev in listCombos[index-1]:        # retrieve the lists from the previous column
                listCur = listPrev[:]                   # create a new temporary list object to update
                listCur.append(item)                    # add the item to the previous list to make it current
                listCombos[index].append(listCur)       # list length and append it to the current list

                itemCombo = ''                          # Create a str to concatenate list items into a str
                for item in listCur:                    # concatenate the members of the lists to create
                    itemCombo += item                   # create a string of items
                listSimple.append(itemCombo)            # add to the final output list

    return [listSimple, listCombos]
# END getCombos()
TiPS
sumber
Jadi yang tampaknya dilakukan oleh kode ini adalah mengembalikan [listOfCombinations, listOfCombinationsGroupedBySize]. Sayangnya ketika dijalankan dengan input demo itu memberikan 63 elemen daripada 64; tampaknya tidak ada set kosong (dalam hal ini, string kosong "").
ninjagecko
2

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:

    lambda l: [(a, b) for i, a in enumerate(l) for b in l[i+1:]]


Dan, untuk kombinasi tiga pasang, semudah ini:

    lambda l: [(a, b, c) for i, a in enumerate(l) for ii, b in enumerate(l[i+1:]) for c in l[i+ii+2:]]


Hasilnya identik dengan menggunakan itertools.combinations:

import itertools
combs_3 = lambda l: [
    (a, b, c) for i, a in enumerate(l) 
    for ii, b in enumerate(l[i+1:]) 
    for c in l[i+ii+2:]
]
data = ((1, 2), 5, "a", None)
print("A:", list(itertools.combinations(data, 3)))
print("B:", combs_3(data))
# A: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]
# B: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]
Cynadyde
sumber
2

Tanpa menggunakan itertools:

def combine(inp):
    return combine_helper(inp, [], [])


def combine_helper(inp, temp, ans):
    for i in range(len(inp)):
        current = inp[i]
        remaining = inp[i + 1:]
        temp.append(current)
        ans.append(tuple(temp))
        combine_helper(remaining, temp, ans)
        temp.pop()
    return ans


print(combine(['a', 'b', 'c', 'd']))
Pradeep Vairamani
sumber
2

Berikut adalah dua implementasi dari itertools.combinations

Salah satu yang mengembalikan daftar

def combinations(lst, depth, start=0, items=[]):
    if depth <= 0:
        return [items]
    out = []
    for i in range(start, len(lst)):
        out += combinations(lst, depth - 1, i + 1, items + [lst[i]])
    return out

Satu mengembalikan generator

def combinations(lst, depth, start=0, prepend=[]):
    if depth <= 0:
        yield prepend
    else:
        for i in range(start, len(lst)):
            for c in combinations(lst, depth - 1, i + 1, prepend + [lst[i]]):
                yield c

Harap dicatat bahwa memberikan fungsi pembantu kepada mereka disarankan karena argumen sebelumnya adalah statis dan tidak berubah dengan setiap panggilan

print([c for c in combinations([1, 2, 3, 4], 3)])
# [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

# get a hold of prepend
prepend = [c for c in combinations([], -1)][0]
prepend.append(None)

print([c for c in combinations([1, 2, 3, 4], 3)])
# [[None, 1, 2, 3], [None, 1, 2, 4], [None, 1, 3, 4], [None, 2, 3, 4]]

Ini adalah kasus yang sangat dangkal tetapi lebih baik aman daripada menyesal

Modar
sumber
2

Bagaimana dengan ini .. menggunakan string bukan daftar, tetapi hal yang sama .. string dapat diperlakukan seperti daftar di Python:

def comb(s, res):
    if not s: return
    res.add(s)
    for i in range(0, len(s)):
        t = s[0:i] + s[i + 1:]
        comb(t, res)

res = set()
comb('game', res) 

print(res)
Apurva Singh
sumber
2

Kombinasi dari itertools

import itertools
col_names = ["aa","bb", "cc", "dd"]
all_combinations = itertools.chain(*[itertools.combinations(col_names,i+1) for i,_ in enumerate(col_names)])
print(list(all_combinations))

Terima kasih

Abhishek
sumber
2

Tanpa itertools Python 3 Anda bisa melakukan sesuatu seperti ini:

def combinations(arr, carry):
    for i in range(len(arr)):
        yield carry + arr[i]
        yield from combinations(arr[i + 1:], carry + arr[i])

dimana awalnya carry = "".

Laurynas Tamulevičius
sumber
2

3 fungsi:

  1. semua kombinasi daftar n elemen
  2. semua kombinasi daftar n elemen yang urutannya tidak berbeda
  3. semua permutasi
import sys

def permutations(a):
    return combinations(a, len(a))

def combinations(a, n):
    if n == 1:
        for x in a:
            yield [x]
    else:
        for i in range(len(a)):
            for x in combinations(a[:i] + a[i+1:], n-1):
                yield [a[i]] + x

def combinationsNoOrder(a, n):
    if n == 1:
        for x in a:
            yield [x]
    else:
        for i in range(len(a)):
            for x in combinationsNoOrder(a[:i], n-1):
                yield [a[i]] + x

if __name__ == "__main__":
    for s in combinations(list(map(int, sys.argv[2:])), int(sys.argv[1])):
        print(s)
Alan Swindells
sumber
Saya sangat suka ini !!! Terima kasih!!! Fungsi kombinatorik Python agak aneh. Dalam matematika "kombinasi" fungsi akan menjadi Variasi, dan "kombinasiNoOrder" sebenarnya kombinasi. Saya kira itu membingungkan orang-orang yang datang ke python dari cabang matematika, seperti yang terjadi pada saya saat ini. Bagaimanapun juga, solusi yang bagus, terima kasih banyak!
Branumić Branislav
1

Ini implementasi saya

    def get_combinations(list_of_things):
    """gets every combination of things in a list returned as a list of lists

    Should be read : add all combinations of a certain size to the end of a list for every possible size in the
    the list_of_things.

    """
    list_of_combinations = [list(combinations_of_a_certain_size)
                            for possible_size_of_combinations in range(1,  len(list_of_things))
                            for combinations_of_a_certain_size in itertools.combinations(list_of_things,
                                                                                         possible_size_of_combinations)]
    return list_of_combinations
Andres Ulloa
sumber
1
Apa pemecahan implementasi Anda lebih baik dari implementasi sebelumnya yang diposting di sini.
user1767754
0

Anda juga dapat menggunakan fungsi powerset dari more_itertoolspaket luar biasa .

from more_itertools import powerset

l = [1,2,3]
list(powerset(l))

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

Kami juga dapat memverifikasi, bahwa memenuhi persyaratan OP

from more_itertools import ilen

assert ilen(powerset(range(15))) == 32_768
Jarno
sumber
-1
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
    return
indices = range(r)
yield tuple(pool[i] for i in indices)
while True:
    for i in reversed(range(r)):
        if indices[i] != i + n - r:
            break
    else:
        return
    indices[i] += 1
    for j in range(i+1, r):
        indices[j] = indices[j-1] + 1
    yield tuple(pool[i] for i in indices)


x = [2, 3, 4, 5, 1, 6, 4, 7, 8, 3, 9]
for i in combinations(x, 2):
    print i
Anoop
sumber
1
Jika saya benar, ini adalah kode persis yang disalin dari dokumentasi python [ docs.python.org/3.6/library/itertools.html ]. Jika demikian, silakan lakukan ref sumbernya.
GabrielChu
pendekatan yang menarik
pelos
-1

Jika seseorang mencari daftar terbalik, seperti saya:

stuff = [1, 2, 3, 4]

def reverse(bla, y):
    for subset in itertools.combinations(bla, len(bla)-y):
        print list(subset)
    if y != len(bla):
        y += 1
        reverse(bla, y)

reverse(stuff, 1)
Expat C
sumber
-1
flag = 0
requiredCals =12
from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)  # allows duplicate elements
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

stuff = [2,9,5,1,6]
for i, combo in enumerate(powerset(stuff), 1):
    if(len(combo)>0):
        #print(combo , sum(combo))
        if(sum(combo)== requiredCals):
            flag = 1
            break
if(flag==1):
    print('True')
else:
    print('else')
Gupta Priyansh
sumber