在Python中计算数组的幂集的最快方法是什么？

Question

给定一个数字列表，比如 x = [1,2,3,4,5]，我需要计算它的幂集（也就是这个列表的所有子集）。现在，我用下面的代码来计算这个幂集，但当我有很多这样的列表（比如有4万个这样的数组）时，速度非常慢。所以我在想有没有什么方法可以加快这个过程。

superset = [sorted(x[:i]+x[i+s:]) for i in range(len(x)) for s in range(len(x))]

我还尝试了以下代码，不过它比上面的代码慢得多。

from itertools import chain, combinations

def powerset(x):
    xx = list(x)
    return chain.from_iterable(combinations(xx, i) for i in range(len(xx)+1))

Answer 1

你可以用一种更高效的方式来表示一个集合的所有子集（也叫幂集）。具体来说，可以让所有的子集都指向原始集合，并且每个子集里包含一个数字，这个数字的二进制位表示哪些元素被包含在这个子集中。这样的话，你就可以通过计算元素的数量，然后用这个数量的位数来遍历整数，从而列出所有的子集。不过，正如评论中提到的，幂集的数量增长得非常快，所以如果能避免计算或遍历幂集，尽量就不要去做。