为什么我的 powerset 函数运行内存不足？

Question

def powerset(x):
    total1 = [[]]
    total2 = [[]]
    for a in x:
        for b in total1:
            c = list(b + [x[a]])
            total2.append(c)
        total1 = total2 
        # the total 1 and total 2 system should prevent it 
        # from creating an infinite loop when we add to the total.

        print (total1)

f = [1,2,3]
g = powerset(f)
print (g)

这是我为数据科学介绍创建幂集的尝试 class。当我运行这个时，我在运行内存不足之前收到 [[], [2]] 作为输出。我不明白为什么它 returns [[], [2]] 也不明白为什么它运行s 内存不足，因为 total1 在循环外被改变了。

变量g应该return是f的幂集。

有人可以解释我做错了什么吗？

Answer 1

在您设置 total1 = total2 的第一个循环之后，这意味着 total1 和 total2 引用相同的列表 .

因此在第二个循环中，您迭代 total1 并更新 total2，相同的列表。在Python（以及大多数编程语言）中，改变一个你迭代的集合是危险的，所以你不断地添加项目到列表，使循环越来越长。

代码本身没有问题。我们可以写成：

def powerset(x):
    result = [[]]
    for xi in x:
        xil = [xi]
        for j in range(len(result)):
            result.append(result[j] + xil)
    return result

虽然它可能看起来像是一些语法重写，但我们在这里对 range(len(result)) 进行迭代 j。请注意，当我们开始 for 循环时，我们只计算 len(result) 一次，因此之后，我们可以安全地更新 total，因为范围对象不再改变。

这会产生：

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

请注意，我们可以使用 itertools.combinations 函数让生活更轻松：

from itertools import combinations

def powerset(x):
    xl = list(x)
    for r in range(len(xl)+1):
        for ri in combinations(xl, r):
            yield ri

然后我们得到：

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

为什么我的 powerset 函数运行内存不足？

Why does my powerset function run out of memory?

python

powerset

为什么我的 powerset 函数 运行 内存不足？

Why does my powerset function run out of memory?

python

powerset

为什么我的 powerset 函数运行内存不足？