聚合数组的子集

Question

我正在研究查找和聚合数组子集的问题。经过几次尝试，我能够使用以下方法一个接一个地打印所有子集：

def print_subsets(arr, curr, idx):

    if idx == len(arr):
        print(curr)
        return
    print_subsets(arr, curr, idx + 1)
    print_subsets(arr, curr + [arr[idx - 1]], idx + 1)

例如，如果我们有函数调用； print_subsets([1,2], [], 0) 我们得到输出为 [],[1],[2],[1,2].

下一步，是否可以使用修改后的递归方法并return将输出作为包含该数组所有子集的列表？

预期输出：[[],[1],[2],[1,2]]。

Answer 1

你知道你可以使用 python built-in itertools 代替：

import itertools as it

arr = [1,2]
subsets = [list(i) for c in range(len(arr)+1) for i in it.combinations(arr,c)]

输出：

>> [[], [1], [2], [1, 2]]

Answer 2

假设您的代码正确打印了所需的 sub-lists，您就快完成了。您只需要 return sub-lists 而不是打印它们：

def print_subsets(arr, curr, idx):
    if idx == len(arr):
       return [curr]
    return print_subsets(...) + print_subsets(...)

（我把 [] 放在 curr 周围，因为你想 return 一个子列表列表，而不仅仅是子列表）。

因此，只要识别出一个子集（递归基本情况）而不是打印它，函数 returns 就可以了。否则它只是聚合和 returns 由递归调用 return 编辑的子集。

有了这个改变，我会把函数重命名为 getSubsets() 之类的名字。我还建议为 curr 和 idx 提供默认值以简化初始调用：

def getSubsets(arr, curr=[], idx=0):
    ...

那么你可以这样称呼它：

subsets = getSubsets(arr)

聚合数组的子集

Aggregating subsets of an array

python

arrays

recursion