我有一个包含15个数字的列表,我需要编写一些代码来生成这些数字的所有32,768种组合。

我已经找到了一些代码(通过谷歌搜索),显然做了我正在寻找的,但我发现代码相当不透明,并谨慎使用它。而且我觉得肯定有更优雅的解决方案。

我唯一想到的就是循环十进制整数1-32768并将其转换为二进制,并使用二进制表示作为筛选器来挑选适当的数字。

有人知道更好的办法吗?使用map(),也许?


当前回答

我在这个话题上有点晚了,但我想我可以帮助别人。

你可以使用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)]```

其他回答

我喜欢这个问题,因为有很多方法来实现它。我决定为未来创造一个参考答案。

在生产中使用什么?

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

我来晚了,但我想分享我找到的解决这个问题的方法: 具体来说,我想要做顺序组合,所以对于“STAR”,我想要“STAR”,“TA”,“AR”,但不是“SR”。

lst = [S, T, A, R]
lstCombos = []
for Length in range(0,len(lst)+1):
    for i in lst:
        lstCombos.append(lst[lst.index(i):lst.index(i)+Length])

可以通过在最后一行之前添加额外的if来过滤重复:

lst = [S, T, A, R]
lstCombos = []
for Length in range(0,len(lst)+1):
    for i in lst:
         if not lst[lst.index(i):lst.index(i)+Length]) in lstCombos:
             lstCombos.append(lst[lst.index(i):lst.index(i)+Length])

如果由于某种原因,这将在输出中返回空白列表,这发生在我身上,我添加:

for subList in lstCombos:
    if subList = '':
         lstCombos.remove(subList)

我想我应该为那些寻求答案的人添加这个函数,而不需要导入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],

这是我的实现

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

正如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。