algorithm - 我如何获得特定订单的电源组？

Question

有一些计算幂集的解决方案，但我在谷歌上找到的这些没有按顺序给出幂集，而我需要它。例如，如果我想要 (1,2,3,4) 的幂集，常用算法为我提供了一个幂集以下顺序:

()
(1)
(2)
(1 2)
(3)
(1 3)
(2 3)
(1 2 3)
(4)
(1 4)
(2 4)
(1 2 4)
(3 4)
(1 3 4)
(2 3 4)
(1 2 3 4)

但我需要的是以下顺序:

()
(1)
(2)
(3)
(4)
(1,2)
(1,3)
(1,4)
(2,3)
(2,4)
(3,4)
(1,2,3)
(1,2,4)
(1,3,4)
(2,3,4)
(1,2,3,4)

因为元素的数量可能非常多，所以不可能计算出整个幂集并在之后对其进行排序。

有人知道吗？

Answer 1

您希望组合按长度排序。在 Python 中你可以这样写:

import itertools

def subsets(iterable):
    "Generate the subsets of elements in the iterable, in order by length."
    items = list(iterable)
    for k in xrange(len(items) + 1):
        for subset in itertools.combinations(items, k):
            yield subset

>>> list(subsets([1,2,3,4]))
[(), (1,), (2,), (3,), (4,), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4),
 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)]

参见 this answer有关生成组合的算法的概述。 (或者您可以查看 Raymond Hettinger 的 Python 实现，itertoolsmodule.c lines 2026f。)