计算列表的powerset

Question

我编写了下面的代码来计算列表的powerset (我们认为列表包含所有不同的元素，尽管这并不重要)。

这个功能还能进一步优化吗？

def powerset(A):
    if A == []:
        return [[]]
    a = A[0]
    incomplete_pset = powerset(A[1:])
    rest = []
    for set in incomplete_pset:
        rest.append([a] + set)
    return rest + incomplete_pset

Answer 1

这是重新发明车轮，因为官方文件给出了一个食谱：

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

通过使用迭代，它有效地解决了内存优化问题。

然而，由于它分散工作的方式，它的效率可能没有那么高。

为了提高代码的内存效率，还可以引入可迭代性。我假设你不关心命令：

def powerset(A):
    if A == []:
        yield []
    else:
        a = A[0]
        for tail in powerset(A[1:]):
            yield tail
            yield [a] + tail

我选择tail是为了避免混淆内置的set函数。

最快的内存效率方法可能是可迭代的，使用灰度码创建一个非递归解决方案，该解决方案在每个yield之间添加或删除单个元素。

而且，FWIW，您的代码可能更像Pythonic。

rest = [] for set in incomplete\_pset: rest.append([a] + set)

可能是

rest = [[a] + tail for tail in incomplete_pset]

有可能我对它的可迭代重写也可能是使用理解的Pythonic语言--我对这一点持开放态度。