打印Powerset时复制

Question

from typing import *
def print_powerset(nums: List[int], n: int):
    def print_subsets(i: int, path: List[int]) -> None:
        for child_index in range(i, n):
            curr_path = path + [nums[child_index]]
            print(curr_path)

            for l in range(child_index + 1, n):
                print_subsets(l, curr_path)

    for k in range(n): 
        print([nums[k]])
    for j in range(1, n): 
        print_subsets(j, [nums[0]])

if __name__ == "__main__":
    nums = [0,1,2,3]
    n = len(nums)
    print_powerset(nums, n)

运行上面的代码将生成以下代码：

"""
[0]
[1]
[2]
[3]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
[0, 1, 3]
[0, 1, 3] <- extra
[0, 2]
[0, 2, 3]
[0, 3]
[0, 2] <- extra
[0, 2, 3] <- extra
[0, 3] <- extra
[0, 3] <- extra
"""

我想不出是什么原因导致复印件被打印出来。我知道还有其他打印powerset的方法，但就我目前的目的而言，我只对上面问题的原因感兴趣。

Answer 1

很难确定导致重复的单个问题：print_subsets(j, [nums[0]])似乎应该是print_subsets(j, [nums[j-1]])。在循环中打印curr_path似乎也不太合适；您正在尝试实现的powerset是否有现有的算法？除了具有重复项之外，您的输出还缺少几个子集。

删除几行代码并将print移到循环之外会给出一个有效的算法，也许这就是您的意思？

def print_powerset(nums: List[int], n: int):
    def print_subsets(i: int, path: List[int]) -> None:
        print(path)
        for child_index in range(i, n):
            print_subsets(child_index+1, path + [nums[child_index]])

    print([])
    for j in range(1, n+1):
        print_subsets(j, [nums[j-1]])

Answer 2

这通过使用递归重新处理问题来解决您的问题。这样做的原因可能是因为您的解决方案不仅仅是因为它有重复项而是错误的，而且它还缺少空集和power集的以下元素：

[1, 2]
[1, 3]
[1, 2, 3]
[2, 3]

对于powerset，您应该使用2^n元素，其中n是输入的长度。因此，在这里，我们应该期望得到长度为16的输出--显然与您得到的结果相同。

无论如何，实现这一点的递归方法是认识到每个n+1 powerset包含n的所有元素，并为每个n添加一个元素，其中添加了+1元素。因此，[0]的电源设置为[[], [0]]，[0, 1]的电源设置为[[], [0], [1], [0, 1]。请注意，最后两个元素是前两个元素，每个元素都添加了1。

将此代码转换为代码相对简单：

def powerset(ls: List[int]) -> List[List[int]]:  # Typing helps us thing about how this works!
    if len(ls) == 0:  # This is our base case.
        return [[]]
    else:
        head = ls[0]  # The first element
        tail = ls[1:]  # Remainder of the list
        tail_component = powerset(tail)  # Get the recursive half
        head_component = [l + [head] for l in tail_component]
        return tail_component + head_component  # Concatenate these lists and return the new powerset

然后我们只需要调用它并迭代结果来打印它：

if __name__ == "__main__":
    nums = [0,1,2,3]
    ps = powerset(nums)
    [print(i) for i in ps]

# This will print out:
[]
[3]
[2]
[3, 2]
[1]
[3, 1]
[2, 1]
[3, 2, 1]
[0]
[3, 0]
[2, 0]
[3, 2, 0]
[1, 0]
[3, 1, 0]
[2, 1, 0]
[3, 2, 1, 0]

请注意，这并不是很有效--特别是我要重新创建很多列表。这是内存密集型的，使用生成器和其他技巧可以更快地完成。然而，我想给你一个算法的直接表示，以证明这种方法比试图通过for循环来做要清楚得多。

要确定原始程序出了什么问题，让我们展开(部分)它：

# for k in range(4)
print([0,1,2,3][0]) -> [0]
print([0,1,2,3][1]) -> [1]
print([0,1,2,3][2]) -> [2]
print([0,1,2,3][3]) -> [3]
# for j in range(1, 4)
print_subsets(1, list([0,1,2,3][0])) -> print_subsets(1, [0])
  # for child_index in range(1, 4)
  curr_path = [0] + [0,1,2,3][1] -> [0, 1]
  print(curr_path) -> [0, 1]
  # for l in range(2, 4)
  print_subsets(2, [0, 1]) -> recurses
  ...

现在，需要注意的是，您的curr_path是从[nums[0]]构建的。这意味着每次迭代的path总是以0开头。您可能要做的就是在for j in range...子句中迭代它。但这是非常混乱的，部分原因是不清楚您的变量何时是索引而不是值，还因为您依赖范围来访问更高级别的列表。这些实践很快就会导致代码的混乱和混乱。

Answer 3

所以第二个嵌套循环不应该在那里。这是我应该怎么写的：

def print_powerset(nums: List[int], n: int):
    def print_subsets(i: int, path: List[int]) -> None:
        curr_path = path + [nums[i]]
        print(curr_path)

        for child_index in range(i + 1, n):
            print_subsets(child_index, curr_path)

    print([])
    for k in range(n): 
        print([nums[k]])
    for start_index in range(n):
        for child_index in range(start_index + 1, n): 
            print_subsets(child_index, [nums[start_index]])

if __name__ == "__main__":
    nums = [0,1,2,3]
    n = len(nums)
    print_powerset(nums, n)