如何按特定顺序获取幂集？

Question

有一些计算幂集的解决方案，但是我在Google上找到的这些解决方案没有按照我需要的顺序给出幂集。 例如，如果我想要(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)

由于元素数量可能非常高，因此不可能计算整个幂集并在之后进行排序。

有人有什么想法吗？

- Achim Wagner

---

如果您想在特定的编程语言中实现此操作，将其标注为此类操作可能有助于避免不正确的关闭。 - Bill the Lizard

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

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

- Gareth Rees

Answer 2

你应该提供一些有关在Google上找到的算法的细节...

但是你可以按照以下方式处理：

第一步：创建一个函数，生成给定有序集合长度为n的所有幂集：

下面是这个函数的可能伪代码：

set={a1, ...ap} //is an ordered set
define f( set , n):
   result = {}
   count=1
   for element in set :
         set.pop(element)
         result.append( { f(set,n-1).AppendtoAllInfirstPosition(element) }) // not sure if I write this well, but you process recursively, poping the sorted value one by one a1...ap and using f(popped set, n-1) you append the sets 
   if length(set)=n:
         return set //you initialise the recurence. the above loop will stop when len(popped(set))=n-1
   return result 

第二步：完成此操作后，您只需确定：

f(set,i) for i in range(len(set)) and you will get your ordered power set.

希望这个能够起到作用并对您有所帮助。

- Ricky Bobby

Answer 3

如果初始集合有N个数字，则幂集将包含2^N个元素。我建议采用以下算法：
算法：
按照元素数量递增的顺序顺序生成初始集合的所有子集。例如，可以通过考虑由k个1和n-k个0组成的数组的所有排列（这也称为掩码）来完成此操作。每个掩码描述一个唯一的子集-我们只需选择位于设置为1的位置上的元素。通过这样做，我们将获得（打印、保存或需要的任何内容）按大小递增排序的所有子集，如果相等，则按出现在初始集合中的元素顺序排序。
复杂度：
迭代2^N个掩码并查看每个掩码中的N个位置将导致O（N * 2^N）的复杂度。
实现：
这是我的C++实现，使用std::next_permutation生成所有具有固定数量的1的掩码。它从标准输入读取一组整数，并顺序生成和打印所有子集到标准输出。请注意，如果不必要，此解决方案不会保存子集：

#include <algorithm>
#include <iostream>
#include <vector>

void calcPowerSet( const std::vector< int >& inputSet )
{
    int n = inputSet.size();
    for( int ones = 0; ones <= n; ++ones )
    {
        std::vector< bool > mask( n, 0 );
        for( int i = 0; i < ones; ++i )
            mask[ i ] = true;           // setting first 'ones' bits to '1'
        do
        {   
           // printing the subset described by current mask
           std::cout << "(";
           for( int i = 0; i < n; ++i )
              if( mask[ i ] )
                  std::cout << ' ' << inputSet[ i ] << ' ';
           std::cout << ")\n";
        }
        while( std::next_permutation( mask.rbegin(), mask.rend() ) ); // generating masks
    }
}


int main ()
{
    int n;
    std::cin >> n;
    std::vector< int > inputSet( n );
    for( int i = 0; i < n; ++i )
        std::cin >> inputSet[ i ];
    calcPowerSet( inputSet );
    return 0;
}

- Grigor Gevorgyan

---

嗨，我喜欢这个算法的概念，特别是它的空间效率。不幸的是，使用反向迭代器的 next_permutation 不会产生所需的顺序（使用 n = 4 进行测试并查看大小为 2 的子集）。然而，使用正向迭代器的 prev_permutation 可以工作。直觉上，一定有办法让 next_permutation 也能够工作，但我无法想到。 - user6732794