Today we are going to talk about the Powerset Algorithm C++:
What is PowerSet?
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 powerset algorithm 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.
Comment below if you have any confusions or concerns.
Where is your empty subset?
leave one space for it, will add that