如何获得列表元素的所有可能组合?

I have a list with 15 numbers in, and I need to write some code that produces all 32,768 combinations of those numbers.

我有一个包含15个数字的列表，我需要编写一些代码来生成这些数字的所有32,768个组合。

I've found some code (by Googling) that apparently does what I'm looking for, but I found the code fairly opaque and am wary of using it. Plus I have a feeling there must be a more elegant solution.

我已经(通过谷歌搜索)找到了一些代码，它们显然完成了我正在寻找的工作，但我发现这些代码相当不透明，并且对使用它们很谨慎。另外，我觉得一定有更好的解决办法。

The only thing that occurs to me would be to just loop through the decimal integers 1–32768 and convert those to binary, and use the binary representation as a filter to pick out the appropriate numbers.

我想到的唯一一件事就是循环遍历十进制整数1-32768并将它们转换成二进制，并使用二进制表示作为一个过滤器来挑选适当的数字。

Does anyone know of a better way? Using map(), maybe?

有人知道更好的方法吗?使用map(),可能吗?

21 个解决方案

#1

Have a look at itertools.combinations:

看看迭代工具。

itertools.combinations(iterable, r)

Return r length subsequences of elements from the input iterable.

返回来自输入iterable的元素的r长度的子序列。

Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, the combination tuples will be produced in sorted order.

组合以字典排序顺序发送。因此，如果输入iterable排序，那么组合元组将按排序顺序生成。

Since 2.6, batteries are included!

从2.6开始，包括电池!

#2

This answer missed one aspect: the OP asked for ALL combinations... not just combinations of length "r".

这个答案漏掉了一个方面:OP要求所有的组合……不只是长度r的组合。

So you'd either have to loop through all lengths "L":

所以你要么需要循环所有长度"L"

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

Or -- if you want to get snazzy (or bend the brain of whoever reads your code after you) -- you can generate the chain of "combinations()" generators, and iterate through that:

或者——如果你想要变得时髦(或者让那些读你代码的人绞尽脑汁)——你可以生成“combination()”生成器的链，并对其进行迭代:

from itertools import chain, combinationsdef all_subsets(ss):    return chain(*map(lambda x: combinations(ss, x), range(0, len(ss)+1)))for subset in all_subsets(stuff):    print(subset)

#3

Here's a lazy one-liner, also using itertools:

这里有一个懒惰的一行程序，也使用迭代工具:

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

Main idea behind this answer: there are 2^N combinations -- same as the number of binary strings of length N. For each binary string, you pick all elements corresponding to a "1".

主要目的是回答:有2 ^ N组合一样——二进制字符串的数量为每个二进制串长度N .,你选择所有元素对应于一个“1”。

items=abc * mask=### | V000 -> 001 ->   c010 ->  b011 ->  bc100 -> a101 -> a c110 -> ab111 -> abc

Things to consider:

事情要考虑:

• This requires that you can call len(...) on items (workaround: if items is something like an iterable like a generator, turn it into a list first with items=list(_itemsArg))
• 这要求您可以对项调用len(…)(解决方案:如果项像生成器一样是可迭代的，那么首先将其转换为list =list(_itemsArg))
• This requires that the order of iteration on items is not random (workaround: don't be insane)
• 这要求对项目的迭代顺序不是随机的(解决方案:不要疯狂)
• This requires that the items are unique, or else {2,2,1} and {2,1,1} will both collapse to {2,1} (workaround: use collections.Counter as a drop-in replacement for set; it's basically a multiset... though you may need to later use tuple(sorted(Counter(...).elements())) if you need it to be hashable)
• 这要求项目是唯一的，否则{2、2、1}和{2、1、1}都将崩溃为{2、1}(解决方案:使用集合)。柜位作为落客代替套;它基本上是一个多重集…尽管您以后可能需要使用tuple(已排序的(Counter(…).elements()))，如果您需要它是耐洗的))

---

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'}]

#4

Here is one using recursion:

这里有一个使用递归的例子:

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

#5

In comments under the highly upvoted answer by @Dan H, mention is made of the powerset() recipe in the itertools documentation—including one by Dan himself. However, so far no one has posted it as an answer. Since it's probably one of the better if not the best approach to the problem—and given a little encouragement from another commenter, it's shown below. The function produces all unique combinations of the list elements of every length possible.

在@Dan H高度推荐的答案下面的评论中，提到了itertools文档中的powerset()配方——包括Dan自己的配方。然而，到目前为止还没有人把它作为答案。既然它可能是解决问题的最好的方法之一，而且得到了另一个评论者的一点鼓励，下面将展示它。该函数生成所有可能长度的列表元素的唯一组合。

Note: If the, subtly different, goal is to obtain only combinations of unique elements, change the line s = list(iterable) to s = list(set(iterable)) to eliminate any duplicate elements. Regardless, the fact that the iterable is ultimately turned into a list means it will work with generators (unlike several of the other answers).

注意:如果有微妙的不同，目标是只获取唯一元素的组合，将行s = list(iterable)改为s = list(set(iterable))，以消除任何重复元素。无论如何，可迭代最终变成列表的事实意味着它将与生成器一起工作(与其他几个答案不同)。

from itertools import chain, combinationsdef 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))

Output:

输出:

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)

#6

I agree with Dan H that Ben indeed asked for all combinations. itertools.combinations() does not give all combinations.

我同意丹的观点，他确实要求所有的组合。combination()不会给出所有的组合。

Another issue is, if the input iterable is big, it is perhaps better to return a generator instead of everything in a list:

另一个问题是，如果输入可迭代性很大，那么最好返回生成器，而不是列表中的所有内容:

iterable = range(10)for s in xrange(len(iterable)+1):  for comb in itertools.combinations(iterable, s):    yield comb

#7

This one-liner gives you all the combinations (between 0 and n items if the original list/set contains n distinct elements) and uses the native method itertools.combinations:

这一行代码提供了所有的组合(如果原始列表/集合包含n个不同的元素，那么0到n个项目之间)，并使用了本机方法itertools。

from itertools import combinationsinput = ['a', 'b', 'c', 'd']output = sum([map(list, combinations(input, i)) for i in range(len(input) + 1)], [])

---

The output will be:

的输出将会是:

[[], ['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']]

---

Try it online:

试一试在线:

http://ideone.com/COghfX

http://ideone.com/COghfX

#8

You can generating all combinations of a list in python using this simple code

您可以使用这个简单的代码在python中生成列表的所有组合

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

Result would be :

结果将是:

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

#9

Here is yet another solution (one-liner), involving using the itertools.combinations function, but here we use a double list comprehension (as opposed to a for loop or sum):

这里还有另一个解决方案(一行)，涉及使用itertools.combination函数，但是这里我们使用双列表理解(与for循环或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)]

#10

Below is a "standard recursive answer", similar to the other similar answer https://*.com/a/23743696/711085 . (We don't realistically have to worry about running out of stack space since there's no way we could process all N! permutations.)

下面是一个“标准递归答案”，类似于其他类似的答案https://*.com/a/23743696/711085。(实际上，我们不必担心堆栈空间用完，因为我们不可能处理所有的N!排列)。

It visits every element in turn, and either takes it or leaves it (we can directly see the 2^N cardinality from this algorithm).

访问每个元素反过来,要么把它或离开它(我们可以直接看到2 ^ N基数从这个算法)。

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

#11

I thought I would add this function for those seeking an answer without importing itertools or any other extra libraries.

我想我应该为那些不需要导入迭代工具或任何其他额外库就能找到答案的人添加这个函数。

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

Simple Yield Generator Usage:

简单的收益率发电机的使用:

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

Output from Usage example above:

以上使用示例输出:

[] , [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] ,

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

#12

I know it's far more practical to use itertools to get the all the combinations, but you can achieve this partly with only list comprehension if you so happen to desire, granted you want to code a lot

我知道使用itertools来获取所有的组合要实用得多，但是如果您碰巧想要编写很多代码，那么您可以只使用列表理解来实现这一点

For combinations of two pairs:

两对组合:

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

And, for combinations of three pairs, it's as easy as this:

对于三对组合，就像这样简单:

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

---

The result is identical to using itertools.combinations:

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

#13

Using list comprehension:

使用列表理解:

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 listCombinedlist2Combine = ['A', 'B', 'C']listCombined = selfCombine( list2Combine, 2 )

Output would be:

输出是:

['A', 'A']['A', 'B']['A', 'C']['B', 'B']['B', 'C']['C', 'C']

#14

This code employs a simple algorithm with nested lists...

该代码使用了一个带有嵌套列表的简单算法。

# 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()

#15

This is my implementation

这是我的实现

    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

#16

Without using itertools:

出现不使用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 ansprint(combine(['a', 'b', 'c', 'd']))

#17

Here are two implementations of itertools.combinations

这里有两个迭代工具的实现。

One that returns a list

返回列表的一个。

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

One returns a 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

Please note that providing a helper function to those is advised because the prepend argument is static and is not changing with every call

请注意，为那些提供了一个helper函数，因为prepend参数是静态的，并且不会随每次调用而改变。

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 prependprepend = [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]]

This is a very superficial case but better be safe than sorry

这是一个非常表面的情况，但最好是安全的而不是遗憾

#18

If someone is looking for a reversed list, like I was:

如果有人正在寻找一个相反的列表，就像我一样:

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)

#19

How about this.. used a string instead of list, but same thing.. string can be treated like a list in Python:

这个怎么样. .用字符串代替list，但还是一样字符串可以像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)

#20

Combination from itertools

结合出现从itertools

import itertoolscol_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))

Thanks

谢谢

#21

def combinations(iterable, r):# combinations('ABCD', 2) --> AB AC AD BC BD CD# combinations(range(4), 3) --> 012 013 023 123pool = tuple(iterable)n = len(pool)if r > n:    returnindices = 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