我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
当前回答
我喜欢这个问题,因为有很多方法来实现它。我决定为未来创造一个参考答案。
在生产中使用什么?
intertools的文档有一个独立的例子,为什么不在你的代码中使用它呢?一些人建议使用more_itertools。Powerset,但它具有完全相同的实现!如果我是你,我不会为一个小东西安装整个软件包。也许这是最好的方法:
import itertools
def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
return itertools.chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
其他可能的方法
方法0:使用组合
import itertools
def subsets(nums):
result = []
for i in range(len(nums) + 1):
result += itertools.combinations(nums, i)
return result
方法1:简单的递归
def subsets(nums):
result = []
def powerset(alist, index, curr):
if index == len(alist):
result.append(curr)
return
powerset(alist, index + 1, curr + [alist[index]])
powerset(alist, index + 1, curr)
powerset(nums, 0, [])
return result
方法2:回溯
def subsets(nums):
result = []
def backtrack(index, curr, k):
if len(curr) == k:
result.append(list(curr))
return
for i in range(index, len(nums)):
curr.append(nums[i])
backtrack(i + 1, curr, k)
curr.pop()
for k in range(len(nums) + 1):
backtrack(0, [], k)
return result
or
def subsets(nums):
result = []
def dfs(nums, index, path, result):
result.append(path)
for i in range(index, len(nums)):
dfs(nums, i + 1, path + [nums[i]], result)
dfs(nums, 0, [], result)
return result
方法3:位掩码
def subsets(nums):
res = []
n = len(nums)
for i in range(1 << n):
aset = []
for j in range(n):
value = (1 << j) & i # value = (i >> j) & 1
if value:
aset.append(nums[j])
res.append(aset)
return res
或者(不是位掩码,直觉上是2^n个子集)
def subsets(nums):
subsets = []
expected_subsets = 2 ** len(nums)
def generate_subset(subset, nums):
if len(subsets) >= expected_subsets:
return
if len(subsets) < expected_subsets:
subsets.append(subset)
for i in range(len(nums)):
generate_subset(subset + [nums[i]], nums[i + 1:])
generate_subset([], nums)
return subsets
方法4:级联
def subsets(nums):
result = [[]]
for i in range(len(nums)):
for j in range(len(result)):
subset = list(result[j])
subset.append(nums[i])
result.append(subset)
return result
其他回答
这种方法可以很容易地移植到所有支持递归的编程语言中(没有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]]
我来晚了,但我想分享我找到的解决这个问题的方法: 具体来说,我想要做顺序组合,所以对于“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)
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')
我同意Dan H的观点,Ben确实要求所有的组合。itertools.combination()不会给出所有的组合。
另一个问题是,如果输入iterable很大,返回一个生成器而不是列表中的所有内容可能会更好:
iterable = range(10)
for s in xrange(len(iterable)+1):
for comb in itertools.combinations(iterable, s):
yield comb
这段代码采用了一个简单的嵌套列表算法…
# 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()