Python 中的幂集算法：+ 和附加到列表之间的区别

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 操作中覆盖幂集中的每个数组。对于 [1, 2, 3] 的输入，我最终得到 return 的值：

[[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

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

想象一下，有一个包含某人 phone 号码的 10 个副本的列表；如果你拨第一个phone号码让他们戴上帽子，那么当你拨第二个phone号码时，那头的人已经戴上了帽子，因为它是同一个人。如果你拨每个号码并每次都说 "put on a hat"，你最终会得到一个包含 10 个 phone 号码的列表，一个人戴着 10 顶帽子，而你实际上想要 phone 个号码代表 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)]

Python 中的幂集算法：+ 和附加到列表之间的区别

Powerset algorithm in Python: difference between + and append on lists

python

python-3.x

algorithm

powerset