我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
当前回答
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')
其他回答
使用列表推导式:
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']
不使用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']))
我喜欢这个问题,因为有很多方法来实现它。我决定为未来创造一个参考答案。
在生产中使用什么?
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的组合
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))
这里是另一个解决方案(一行程序),涉及到使用itertools.combination函数,但这里我们使用了双链表理解式(而不是for循环或sum):
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)]