如何获取列表元素的所有可能组合？

Question

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

我发现了 一些代码 （通过谷歌搜索）这显然符合我的要求，但我发现代码相当不透明，并且对使用它持谨慎态度。另外我有一种感觉必须有一个更优雅的解决方案。

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

有谁知道更好的方法吗？使用 map(), ， 或许？

Answer 1

看一看 itertools.combinations ：

itertools.combinations(iterable, r)

     

从元件的返回ř长度的子序列   输入可迭代。

     

组合被发射在词典排序顺序。因此，如果   输入可迭代进行排序，所述   组合的元组将在生产   排序顺序。

由于2.6，电池包括！

Answer 2

此答案错过一个方面：要求的所有组合的OP ...不只是长度的“R”的组合

所以你要么必须通过所有的长度“L”的循环：

import itertools

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

或者 - 如果你想时髦（或弯曲后你谁读你的代码的大脑） - 你可以生成的“组合（）”发电机链，并通过迭代：

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)

Answer 3

这里有一个懒惰的一个衬垫，还使用的迭代:

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

主要想法的背后这个答案:有2^N组合--同的二进制数字符串的长N.每个binary string,你选择的所有元素相对应的一个"1".

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

要考虑的事项：

• 这需要，你能打电话 len(...) 上 items (解决办法：如果 items 就像是一个迭代喜欢一个发电机，把它变成一个列表中第一个与 items=list(_itemsArg))
• 这要求顺序的迭代 items 不是随机的(解决办法：不是疯了)
• 这需要，项目是独特的，或者别的 {2,2,1} 和 {2,1,1} 将两者崩溃 {2,1} (解决办法：使用 collections.Counter 作为替换为 set;它基本上是一个多集...虽然你可能需要以后使用 tuple(sorted(Counter(...).elements())) 如果你需要哈希)

---

演示

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

Answer 4

在评论下得到了高度评​​价 回答 @Dan H，提到了 powerset() 食谱中的 itertools 文档——包括一位 丹本人. 然而, ，到目前为止还没有人将其作为答案发布。因为它可能是解决问题的更好的方法之一，即使不是最好的方法，并且考虑到 小小的鼓励 来自另一位评论者，如下所示。该函数产生 全部 列表元素的独特组合 每一个 可能的长度（包括包含零和所有元素的长度）。

笔记:如果略有不同，目标是仅获得独特元素的组合，请更改该行 s = list(iterable) 到 s = list(set(iterable)) 消除任何重复的元素。无论如何，事实是 iterable 最终变成了一个 list 意味着它将与生成器一起使用（与其他几个答案不同）。

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

输出：

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)

Answer 5

下面是一个使用递归：

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

Answer 6

这句话为您提供了所有组合（之间 0 和 n 项目如果原始列表/集合包含 n 不同的元素）并使用本机方法 itertools.combinations:

蟒蛇2

from itertools import combinations

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

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

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

---

输出将是：

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

---

网上试试：

http://ideone.com/COghfX

Answer 7

我和Dan ^ h同意本确实要求全部的组合。 itertools.combinations()不给所有组合。

另一个问题是，如果输入迭代大，这也许是最好的一个列表返回发电机，而不是一切：

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

Answer 8

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

import itertools

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

<强>结果将是：

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

Answer 9

我以为我会添加这个功能对于那些寻求一个答案，但不导入itertools或任何其他额外的库。

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

简单收率发生器用法：

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

这使用例如上述输出：

  

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

Answer 10

下面是另一种溶液（单行），使用itertools.combinations功能涉及，但这里我们使用双列表解析（而不是一个for循环或总和）：

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

---

演示：

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

Answer 11

这是可以很容易地转移到支撑递归的（无itertools，没有产量，没有列表理解）所有的编程语言的方法：

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

Answer 12

它可以使用itertools来完成

：用于置换

此方法需要一个列表作为输入，并返回包含长度为L的置换以列表的形式的元组的对象列表。

# A Python program to print all  
# permutations of given length 
from itertools import permutations 

# Get all permutations of length 2 
# and length 2 
perm = permutations([1, 2, 3], 2) 

# Print the obtained permutations 
for i in list(perm): 
    print (i) 

：用于组合

此方法需要一个列表和输入R作为输入，并返回其含有以列表的形式长度r的所有可能的组合的元组的对象列表。

# A Python program to print all  
# combinations of given length 
from itertools import combinations 

# Get all combinations of [1, 2, 3] 
# and length 2 
comb = combinations([1, 2, 3], 2) 

# Print the obtained combinations 
for i in list(comb): 
    print (i) 

见此

Answer 13

下面是一个“标准递归答案”，类似于其它类似的回答 https://stackoverflow.com/a/23743696/ 711085个。 （我们不实事求是担心用完堆栈空间，因为没有办法，我们可以处理所有N！排列。）

有访问反过来每个元素，并且或者采取它或离开它（我们可以直接看到来自该算法的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],)

---

演示：

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

Answer 14

此代码采用一种简单的算法与嵌套列表...

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

Answer 15

我知道这是更为实际使用itertools获得的所有的组合，但你的可以的实现这一部分只有列表中理解，如果你这么碰巧的愿望，理所当然要编码的很多

有关2对组合：

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

，点击 而且，对于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:]]

---

其结果是相同的使用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)]

Answer 16

在不使用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']))

Answer 17

下面是itertools.combinations的两个实现

一返回一个列表

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

一个返回一个生成

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

请注意，提供了一个辅助函数来这些建议，因为在前面加上参数是静态的，而不是与每一个电话改变

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

这是一个很浅的情况下，但更好的安全比遗憾

Answer 18

这个怎么样..使用的字符串，而不是名单，但同样的事情..字符串可以像在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)

Answer 19

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

由于

Answer 20

没有 itertools在Python 3，你可以做这样的事情：

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

其中最初carry = "".

Answer 21

使用列表理解：

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 )

输出将是：

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

Answer 22

这是我的执行

    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

Answer 23

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

Answer 24

如果有人正在寻找一个反向列表，就像我是：

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)