如何获得特定顺序的电源？ [英] How do I get a power set in a specific order?

问题描述

有些计算功率集的解决方案，但是我在Google上发现的这些解决方案并没有按顺序提供功率集，而我需要它。
例如，如果我想要（1,2,3,4）的幂集，常用算法为我提供
中的幂集以下顺序：

there some solutions for calculating a power set, but these I found on google doesn't give the power set in the order, which I need it. For example, if I want the power set of (1,2,3,4) common algorithms provide me with a power set in the following order:

()
(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)

但是我需要的是以下命令：

But what I need is the following order:

()
(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)

由于元素数量可能很高，因此无法计算

Because the number of elements can be quite high, it is not possible to calculate the whole power set and order it afterwards.

有人知道吗？

推荐答案

您希望按长度顺序组合。在Python中，您可以编写：

You want the combinations in order by length. In Python you can write:

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

请参见此答案概述生成组合的算法。 （或者，您可以查看Raymond Hettinger的Python实现， itertoolsmodule.c行2026f 。）

See this answer for an overview of algorithms that generate combinations. (Or you can look at Raymond Hettinger's Python implementation, itertoolsmodule.c lines 2026f.)

这篇关于如何获得特定顺序的电源？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！