我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
当前回答
下面是一个惰性一行代码,同样使用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
需要考虑的事情:
This requires that you can call len(...) on items (workaround: if items is something like an iterable like a generator, turn it into a list first with items=list(_itemsArg)) This requires that the order of iteration on items is not random (workaround: don't be insane) This requires that the items are unique, or else {2,2,1} and {2,1,1} will both collapse to {2,1} (workaround: use collections.Counter as a drop-in replacement for set; it's basically a multiset... though you may need to later use tuple(sorted(Counter(...).elements())) if you need it to be hashable)
Demo
>>> 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'}]
其他回答
这段代码采用了一个简单的嵌套列表算法…
# 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()
如果你不想使用组合库,这里是解决方案:
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]]
这个怎么样?使用字符串而不是列表,但同样的事情..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)
这一行代码给出了所有的组合(如果原始列表/set包含n个不同的元素,则在0到n个元素之间),并使用本机方法itertools.combination:
Python 2
from itertools import combinations
input = ['a', 'b', 'c', 'd']
output = sum([map(list, combinations(input, i)) for i in range(len(input) + 1)], [])
Python 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']]
在网上试试吧:
http://ideone.com/COghfX
下面是一个“标准递归答案”,类似于其他类似的答案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