我有一个包含 15 个数字的列表，我需要编写一些代码来生成这些数字的所有 32,768 个组合。
我发现一些代码（通过谷歌搜索）显然可以满足我的要求，但我发现代码相当不透明并且对使用它持谨慎态度。另外，我觉得必须有一个更优雅的解决方案。
我唯一想到的就是循环遍历十进制整数 1-32768 并将它们转换为二进制，然后使用二进制表示作为过滤器来挑选出适当的数字。
有人知道更好的方法吗？使用map()，也许？
Ben
问问题
1014522 次
30 回答
742
这个答案错过了一个方面：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)
或者——如果你想变得时髦（或者让阅读你代码的人的大脑弯曲）——你可以生成“combinations()”生成器链，并遍历它：
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)
于 2011-05-05T12:56:24.243 回答
618
itertools.combinations(iterable, r)从输入可迭代中返回 r 个长度的元素子序列。
组合按字典排序顺序发出。因此，如果输入的可迭代对象已排序，则组合元组将按排序顺序生成。
从 2.6 开始，包括电池！
于 2009-01-21T11:20:04.160 回答
60
这是一个懒惰的单线，也使用 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)) )
这个答案背后的主要思想：有 2^N 组合 - 与长度为 N 的二进制字符串的数量相同。对于每个二进制字符串，您选择与“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'}]
于 2011-07-01T00:21:10.823 回答
57
在@Dan H 高度赞成的回答下的评论中，提到了文档powerset()中的配方——包括Dan 自己的配方。但是，到目前为止，没有人将其发布为答案。由于它可能是解决问题的最佳方法之一，如果不是最好的方法，并且得到另一位评论者的一点鼓励，如下所示。该函数生成每个可能长度的列表元素的所有唯一组合（包括那些包含零和所有元素的组合）。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)
于 2016-12-06T01:45:35.240 回答
43
这个单线为您提供所有组合（如果原始列表/集合包含不同的元素，则为项目之间的0和项目）并使用本机方法：nnitertools.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']]
在线尝试：
于 2014-06-25T07:08:01.400 回答
42
这是一个使用递归的例子：
>>> 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']
于 2014-05-19T17:25:51.250 回答
42
这是一种可以很容易地转移到所有支持递归的编程语言（没有 itertools，没有 yield，没有列表理解）的方法：
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]]
于 2019-02-01T13:02:27.973 回答
28
您可以使用以下简单代码在 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)]
于 2015-03-17T05:52:28.243 回答
22
我同意 Dan H 的观点，Ben 确实要求所有组合。itertools.combinations()没有给出所有组合。
另一个问题是，如果输入迭代很大，最好返回一个生成器而不是列表中的所有内容：
iterable = range(10)
for s in xrange(len(iterable)+1):
for comb in itertools.combinations(iterable, s):
yield comb
于 2011-08-24T10:24:55.047 回答
20
我想我会为那些在不导入 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] ,
于 2016-12-20T04:29:07.627 回答
9
这是另一个解决方案（单线），涉及使用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)]
于 2015-09-14T00:13:02.740 回答
9
3个功能：
- n 个元素的所有组合列表
- n 元素列表的所有组合，其中顺序不明确
- 所有排列
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)
于 2020-03-03T19:35:16.647 回答
8
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))
输出
[
['A'],
['B'],
['C'],
['A', 'B'],
['A', 'C'],
['B', 'C'],
['A', 'B', 'C']
]
于 2019-11-23T15:43:56.287 回答
8
您还可以使用优秀软件包中的powerset功能。more_itertools
from more_itertools import powerset
l = [1,2,3]
list(powerset(l))
# [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
我们还可以验证它是否符合 OP 的要求
from more_itertools import ilen
assert ilen(powerset(range(15))) == 32_768
于 2020-05-05T16:27:29.120 回答
6
以下是“标准递归答案”，类似于其他类似答案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
于 2015-09-13T23:28:46.337 回答
4
我知道使用 itertools 来获取所有组合要实用得多，但是如果你碰巧想要编写很多代码，你可以部分地通过列表理解来实现这一点
对于两对的组合：
lambda l: [(a, b) for i, a in enumerate(l) for b in l[i+1:]]
而且，对于三对的组合，就这么简单：
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)]
于 2017-10-06T16:08:32.030 回答
3
这里有两个实现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
请注意，建议为那些提供帮助函数，因为 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 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]]
这是一个非常肤浅的案例，但最好是安全而不是抱歉
于 2017-11-06T09:01:08.323 回答
3
这个怎么样..使用字符串而不是列表，但同样的事情..字符串可以被视为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)
于 2017-12-17T18:04:33.027 回答
3
来自 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))
于 2017-12-19T16:23:42.837 回答
3
如果没有 itertoolsPython 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 = "".
于 2018-10-12T12:59:42.657 回答
2
这段代码采用了一个简单的算法和嵌套列表......
# 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()
于 2015-05-01T05:07:03.430 回答
2
这是我的实现
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
于 2017-02-05T03:42:55.247 回答
2
不使用 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']))
于 2017-10-22T00:57:26.393 回答
1
使用列表理解：
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']
于 2011-08-21T19:10:24.223 回答
1
我迟到了，但想分享我找到的解决同一问题的解决方案：具体来说，我正在寻找顺序组合，所以对于“STAR”，我想要“STAR”、“TA”、“AR”，但不是“SR”。
lst = [S, T, A, R]
lstCombos = []
for Length in range(0,len(lst)+1):
for i in lst:
lstCombos.append(lst[lst.index(i):lst.index(i)+Length])
可以通过在最后一行之前添加额外的 if 来过滤重复项：
lst = [S, T, A, R]
lstCombos = []
for Length in range(0,len(lst)+1):
for i in lst:
if not lst[lst.index(i):lst.index(i)+Length]) in lstCombos:
lstCombos.append(lst[lst.index(i):lst.index(i)+Length])
如果由于某种原因这会在输出中返回空白列表，这发生在我身上，我补充说：
for subList in lstCombos:
if subList = '':
lstCombos.remove(subList)
于 2020-10-30T21:17:32.947 回答
0
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 = list(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
于 2016-05-07T19:17:02.480 回答
0
如果有人正在寻找一个反向列表，就像我一样：
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)
于 2017-12-04T06:54:39.297 回答
0
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')
于 2019-09-04T19:59:48.897 回答
0
如果您不想使用组合库，这里是解决方案：
nums = [1,2,3]
p = [[]]
fnl = [[],nums]
for i in range(len(nums)):
for j in range(i+1,len(nums)):
p[-1].append([i,j])
for i in range(len(nums)-3):
p.append([])
for m in p[-2]:
p[-1].append(m+[m[-1]+1])
for i in p:
for j in i:
n = []
for m in j:
if m < len(nums):
n.append(nums[m])
if n not in fnl:
fnl.append(n)
for i in nums:
if [i] not in fnl:
fnl.append([i])
print(fnl)
输出：
[[], [1, 2, 3], [1, 2], [1, 3], [2, 3], [1], [2], [3]]
于 2021-08-05T05:29:35.173 回答
0
在组合大小上递归的另一种解决方案：
def _comb(items, i, res, pos):
if len(items) == i:
return
res += [r + [c] for c in items for r in res[pos:]]
# Combinations are like a tree, and "pos" is the leaves index
# where we build the new sub tree
_comb(items,i+1, res, len(items)**i+pos)
def comb(items):
l = [[]]
_comb(items, 0, l, 0)
return l
于 2022-02-07T07:15:29.720 回答