python - Python 中的幂集算法 : difference between + and append on lists

Question

我正在解决 Python 中的幂集问题。

集合 S 的幂集 P(S) 是 S 的所有子集的集合。例如，如果 S = {a, b, c} 那么 P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}。

这个解决方案工作得很好:

def powerset(array):
    powerset = [[]]
    for num in array:
        for i in range(len(powerset)):
            curr_subset = powerset[i]
            powerset.append(curr_subset + [num])
    return powerset

但是，此解决方案不会:

def powerset(array):
    powerset = [[]]
    for num in array:
        for i in range(len(powerset)):
            curr_subset = powerset[i]
            curr_subset.append(num)
            powerset.append(curr_subset)
    return powerset

似乎在每个 powerset.append 操作中覆盖 powerset 中的每个数组。对于 [1, 2, 3] 的输入，我最终得到一个返回值:

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

知道我在这里没有完全理解的地方吗？

Answer 1

您的算法的问题在于列表是可变的，并且您正在创建一个充满对同一列表的引用的列表。任何时候你附加到其中一个，你就附加到所有的，因为只有一个。它们都是同一个列表，您只是对其有多个引用。

想象一下，有一个包含某人电话号码的 10 个副本的列表；如果你拨第一个电话号码让他们戴上帽子，那么当你拨第二个电话号码时，那头的人已经戴上了帽子，因为是同一个人。如果您调用每个号码并每次都说“戴上帽子”，您最终会得到一个包含 10 个电话号码的列表，一个人戴 10 顶帽子，而实际上您需要 10 个人戴一顶帽子的电话号码。

设计这种算法最简单的方法就是完全避免变异；使用元组而不是列表。这样，每次您向元组添加另一个元素时，您都在创建一个新元组而不是更改现有元组。

请注意，这与您使用 curr_subset + [num] 的第一个解决方案非常相似； + 操作会创建一个新列表，这与 append 不同，它会更改现有列表的状态。

def powerset(array):
    # a list containing an empty tuple
    powerset = [()]

    for num in array:
        for i in range(len(powerset)):
            curr_subset = powerset[i]
            # append one more number to the tuple
            curr_subset += (num,)
            powerset.append(curr_subset)

    return powerset

例子:

>>> powerset([1, 2, 3])
[(), (1,), (2,), (1, 2), (3,), (1, 3), (2, 3), (1, 2, 3)]