Powerset Algorithm in C++


A powerset of a given set is the combination of all subsets, including the empty subset and the set itself. Suppose we have the following set: {1,2,3}. Its powerset would be:

{1,2,3} 
{1,2}
{1,3}
{2,3}
{1}
{2}
{3}

Creating an algorithm to generate a powerset is not trivial. The first idea you can use is to implement an iterative algorithm that uses a stack to grow and shrink the set as needed. The benefit of this approach is that it prints the subsets in lexicographic order. Below you’ll find an implementation in C++ that prints the powerset of the set 1,2,3… n (where you can specify n in the program):

#include <iostream>

void printSet(int array[],int size){
    int i;

    for (i=1;i<=size;i++)
        std::cout << array[i] << " ";
    std::cout << std::endl;

    return;
}

void printPowerset (int n){
    int stack[10],k;

    stack[0]=0; /* 0 is not considered as part of the set */
    k = 0;

    while(1){
        if (stack[k]<n){
            stack[k+1] = stack[k] + 1;
            k++;
        }

        else{
            stack[k-1]++;
            k--;
        }

        if (k==0)
            break;

        printSet(stack,k);
    }

    return;
}

int main(){

    printPowerset(4);

    return 0;
}

The output for the set {1,2,3,4} is this:

1
1 2
1 2 3
1 2 3 4
1 2 4
1 3
1 3 4
1 4
2
2 3
2 3 4
2 4
3
3 4
4

You can also implement the same idea with recursion. The main recursive function would look like this (s is again the stack, k the position, m the starting number of the set and n the last number):

void powersetRec(int s[], int k; int m, int n) {
    if (m <= n) {
        s[k+1] = m ;
        printSet(s, k+1) ; 
        powersetRec(s, k+1, m+1, n) ; /* with m */
        powersetRec(s, k, m+1, n) ; /*  without m */
    }
}

If you want to perform something with the set elements other than print them you’ll just need to modify the printSet() function.


One thought on “Powerset Algorithm in C++

  1. Lutu Putu

    In printPowerset( ); I can input just the number of elements starting form 1(one) to that element.
    But I need the inputs from user. That is, the user gives the number of elements, as well as the elements also. The elements can be anything- integers or even string.
    How can I modify by this?
    Thanks in advance.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *