我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
当前回答
你可以使用以下简单的代码在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.combination的两个实现
返回一个列表的函数
def combinations(lst, depth, start=0, items=[]):
if depth <= 0:
return [items]
out = []
for i in range(start, len(lst)):
out += combinations(lst, depth - 1, i + 1, items + [lst[i]])
return out
一个返回一个生成器
def combinations(lst, depth, start=0, prepend=[]):
if depth <= 0:
yield prepend
else:
for i in range(start, len(lst)):
for c in combinations(lst, depth - 1, i + 1, prepend + [lst[i]]):
yield c
请注意,建议为它们提供一个helper函数,因为prepend参数是静态的,不会随着每次调用而改变
print([c for c in combinations([1, 2, 3, 4], 3)])
# [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
# get a hold of prepend
prepend = [c for c in combinations([], -1)][0]
prepend.append(None)
print([c for c in combinations([1, 2, 3, 4], 3)])
# [[None, 1, 2, 3], [None, 1, 2, 4], [None, 1, 3, 4], [None, 2, 3, 4]]
这是一个很肤浅的例子,但小心为妙
这个怎么样?使用字符串而不是列表,但同样的事情..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)
这里是另一个解决方案(一行程序),涉及到使用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)]
看看itertools.combination:
itertools.combinations (iterable, r) 返回元素的r长度子序列 输入迭代对象。 组合是按字典排序顺序发出的。那么,如果 Input iterable已排序,则 组合元组将在 排序顺序。
从2.6开始,电池包括在内!
正如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。