如何获得按特定顺序排列的功率？

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) 

因为元素的数量可能相当高，不可能计算整个功率集并在之后进行排序。

有没有人有一些想法？

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。）

Answer 2

（你应该给你在谷歌找到了一些算法的细节...）

但你可以处理这种方式：

第一：创建生成的所有电源设置功能给定一组有序的长度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. 

希望这个作品，它由长度有助于

Answer 3

如果初始集合有N个数字，那么功率集合将包含2^N个元素。我建议以下

算法：
Sequently产生inital集的所有子集在增加他们的元素数量的订单。例如，这可以通过考虑由k个和n-k个零（这也称为掩码）组成的阵列的所有排列来完成。每个蒙版描述了一个独特的子集 - 我们只需选取位置设置为1的元素。通过这个，我们将得到（打印，保存或者需要的任何东西）所有通过增加它们的大小而排序的子集，如果相等，则按照出现在初始集合中的元素的顺序。

复杂性：
迭代2^N面具，看着每个N位置将导致我们O(N * 2^N)复杂性。

实现：
这是我在C++实现，使用std::next_permutation生成固定数量的ones所有面具。它从标准输入中读取一组整数，然后生成并打印所有子集到标准输出。请注意，此解决方案不保存的子集，如果没有必要的：

#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; 
}