我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。
我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。
我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。
有人知道更好的办法吗?使用map(),也许?
当前回答
正如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。
其他回答
正如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。
下面是一个使用递归的例子:
>>> 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']
这是我的实现
def get_combinations(list_of_things):
"""gets every combination of things in a list returned as a list of lists
Should be read : add all combinations of a certain size to the end of a list for every possible size in the
the list_of_things.
"""
list_of_combinations = [list(combinations_of_a_certain_size)
for possible_size_of_combinations in range(1, len(list_of_things))
for combinations_of_a_certain_size in itertools.combinations(list_of_things,
possible_size_of_combinations)]
return list_of_combinations
这一行代码给出了所有的组合(如果原始列表/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
我想我应该为那些寻求答案的人添加这个函数,而不需要导入itertools或任何其他额外的库。
def powerSet(items):
"""
Power set generator: get all possible combinations of a list’s elements
Input:
items is a list
Output:
returns 2**n combination lists one at a time using a generator
Reference: edx.org 6.00.2x Lecture 2 - Decision Trees and dynamic programming
"""
N = len(items)
# enumerate the 2**N possible combinations
for i in range(2**N):
combo = []
for j in range(N):
# test bit jth of integer i
if (i >> j) % 2 == 1:
combo.append(items[j])
yield combo
简单Yield Generator用法:
for i in powerSet([1,2,3,4]):
print (i, ", ", end="")
以上用法示例的输出:
[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4]. [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4],