在python中具有powerset的问题

Question

我正在解决python中的powerset问题：

集合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)]