我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
当前回答
如果你不想使用组合库,这里是解决方案:
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]]
其他回答
下面是一个使用递归的例子:
>>> 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']
这段代码采用了一个简单的嵌套列表算法…
# 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()
正如James Brady提到的,你的itertools.combination是一个键。但这并不是一个完整的解决方案。
解决方案1
import itertools
def all(lst):
# ci is a bitmask which denotes particular combination,
# see explanation below
for ci in range(1, 2**len(lst)):
yield tuple(itertools.compress(
lst,
[ci & (1<<k) for k in range(0, len(lst))]
))
解决方案2
import itertools
def all_combs(lst):
for r in range(1, len(lst)+1):
for comb in itertools.combinations(lst, r):
yield comb
例子
>>> list(all_combs([1,2,3]))
[(1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)]
>>> len(list(all_combs([1,2,3])))
7
>>> len(list(all_combs(range(0, 15))))
32767
>>> list(all([1,2,3]))
[(1,), (2,), (1, 2), (3,), (1, 3), (2, 3), (1, 2, 3)]
>>> len(list(all(range(15))))
32767
解释
假设数组A的长度为N,让长度为N的位掩码B表示一个特定的组合C。如果B[i]是1,那么A[i]属于组合C。
方案1说明
所以我们可以遍历所有的位掩码并用这个位掩码过滤源数组A,这可以通过itertools。compress来完成。
方案2说明
...或者,我们可以用组合来表示
现在我们需要考虑这样的情况,当B中只有一个1,然后只有两个1,等等。每种情况都属于特定的组合。 因此,一旦我们组合所有的组合集,我们将得到所有的子序列。
同样,很明显,在这种情况下,所有可能的组合的数量是2^N - 1。当所有B[i]都为零时,我们省略大小写,因为我们假设空集不是一个组合。否则,就不要减去1。
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')
这个怎么样?使用字符串而不是列表,但同样的事情..string可以像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)