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.
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.
If you can explain the algorithm first then it’s good. Directly looking at code scarying me.