How do I get a power set in a specific order?

Question

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.

Has anyone some idea?

Answer 1

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

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

Answer 2

(You should give some details about the algorithms you found on google...)

But you can process this way:

first : Create a function that generate all the power sets of length n of a given ordered set:

here is a possible pseudo code for this function:

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 

Second : Once you done this you just determinate :

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

Hope this works and it helps

Answer 3

If the initial set has N numbers the power set will contain 2^N elements. I suggest the following

Algorithm:
Sequently generate all subsets of inital set in order of increasing their number of elements. This can be done, for example, by considering all permutations of an array, consisting of k ones and n-k zeroes (this is also called mask). Each mask describes a unique subset - we just pick the elements standing on the positions which are set to 1. By this we will get (print, save or whatever is needed) all the subsets ordered by increasing their size, if equal then by order of elements appearing in the initial set.

Complexity:
Iterating 2^N masks and looking at N positions in each will lead us to O( N * 2^N ) complexity.

Implementation:
Here is my implementation in C++, using std::next_permutation to generate all masks with fixed number of ones. It reads a set of integers from standard input and sequently generates and prints all subsets to standard output. Note that this solution does not save the subsets, if it is not necessary:

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