我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
当前回答
这段代码采用了一个简单的嵌套列表算法…
# 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()
其他回答
这个怎么样?使用字符串而不是列表,但同样的事情..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)
我喜欢这个问题,因为有很多方法来实现它。我决定为未来创造一个参考答案。
在生产中使用什么?
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
你可以使用以下简单的代码在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)]
我在这个话题上有点晚了,但我想我可以帮助别人。
你可以使用itertools中的product:
from itertools import product
n = [1, 2, 3]
result = product(n, repeat=3) # You can change the repeat more then n length
print(list(result))
输出:
[(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 3, 1),
(1, 3, 2), (1, 3, 3), (2, 1, 1), (2, 1, 2), (2, 1, 3), (2, 2, 1), (2, 2, 2),
(2, 2, 3), (2, 3, 1), (2, 3, 2), (2, 3, 3), (3, 1, 1), (3, 1, 2), (3, 1, 3),
(3, 2, 1), (3, 2, 2), (3, 2, 3), (3, 3, 1), (3, 3, 2), (3, 3, 3)]
另一个例子,但是改变了repeat参数:
from itertools import product
n = [1, 2, 3]
result = product(n, repeat=4) # Changing repeat to 4
print(list(result))
输出:
(1, 1, 2, 3), (1, 1, 3, 1), (1, 1, 3, 2), (1, 1, 3, 3), (1, 2, 1, 1),
(1, 2, 1, 2), (1, 2, 1, 3), (1, 2, 2, 1), (1, 2, 2, 2), (1, 2, 2, 3),
(1, 2, 3, 1), (1, 2, 3, 2), (1, 2, 3, 3), (1, 3, 1, 1), (1, 3, 1, 2),
(1, 3, 1, 3), (1, 3, 2, 1), (1, 3, 2, 2), (1, 3, 2, 3), (1, 3, 3, 1),
(1, 3, 3, 2), (1, 3, 3, 3), (2, 1, 1, 1), (2, 1, 1, 2), (2, 1, 1, 3),
(2, 1, 2, 1), (2, 1, 2, 2), (2, 1, 2, 3), (2, 1, 3, 1), (2, 1, 3, 2),
(2, 1, 3, 3), (2, 2, 1, 1), (2, 2, 1, 2), (2, 2, 1, 3), (2, 2, 2, 1),
(2, 2, 2, 2), (2, 2, 2, 3), (2, 2, 3, 1), (2, 2, 3, 2), (2, 2, 3, 3),
(2, 3, 1, 1), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 1), (2, 3, 2, 2),
(2, 3, 2, 3), (2, 3, 3, 1), (2, 3, 3, 2), (2, 3, 3, 3), (3, 1, 1, 1),
(3, 1, 1, 2), (3, 1, 1, 3), (3, 1, 2, 1), (3, 1, 2, 2), (3, 1, 2, 3),
(3, 1, 3, 1), (3, 1, 3, 2), (3, 1, 3, 3), (3, 2, 1, 1), (3, 2, 1, 2),
(3, 2, 1, 3), (3, 2, 2, 1), (3, 2, 2, 2), (3, 2, 2, 3), (3, 2, 3, 1),
(3, 2, 3, 2), (3, 2, 3, 3), (3, 3, 1, 1), (3, 3, 1, 2), (3, 3, 1, 3),
(3, 3, 2, 1), (3, 3, 2, 2), (3, 3, 2, 3), (3, 3, 3, 1), (3, 3, 3, 2),
(3, 3, 3, 3)]```
这个答案漏掉了一个方面:OP要求所有的组合……不仅仅是长度为r的组合。
所以你要么要遍历所有长度为L的循环:
import itertools
stuff = [1, 2, 3]
for L in range(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)