Power Set of String in Lexicographic order

In this article, we have explored what is the meaning of Power Set of String and the algorithm to generate Power Set of String in Lexicographic order.

Table of contents

1. Power Set
2. Lexicographic order
3. What is Power set of string in Lexicographic order?
4. Algorithm
5. Complextiy

Power Set

We are all familiar with term "SET" at somewhere, probably in set theory (or in mathematics).
What is set? The answer is "It is a collection of well defined unordered distinct objects".
Example:

1. The collection of all tall boys in the class.
   It is not a set, because we do not know that which height we can treat as tall.
2. The collection of all tall boys whose height is greater or equal to 165cm in the class.
   It is a set.

What is Power Set ? "It is a collection of all possible subsets of a given set is called Power Set". The power set of 'A' is denoted by P(A).

Example:

1. Given set S: {a, b}
   Then Power set P(S): {" ", a, b, ab}
   Note: Taking " " as NULLSET.
2. Set S: {a, b, c}
   Power set P(S): {" ", a, b, c, ab, ac, bc, abc}

Now, Formula to find the number of elements in Power Set,
Lets take Set A: {a, b, c}, Number of elements in Set 'A' are 3, and the power set P(A): {" ", a, b, c, ab, ac, bc, abc} and Number of elements in P(A) are C(3,0) + C(3,1) + C(3,2) + C(3,3) = 8.

Therefore, If Number of elements in Set A are 'N', then Number of elements in Power Set P(A) are ( C(N,0) + C(N,1) + C(N,2) + . . . + C(N,N) ) = 2^N.

Lexicographic order

Lexicographic order is a way of ordering words in alphabatical order based on their components alphabets. It is also known as Dictionary Order.
Example: algorithm, worst, average, best
Lexicographic order: algorithm, average, best, worst

Power Set of String in Lexicographic order

In this, we are given a string S, we have to find the power set of this string in lexicographical order and print them.
Example:
Say S: {a, b, c}
Power set P(S): {" ", a, b, c, ab, ac, bc, abc}

Output should look like: [ " ", a, ab, abc, ac, b, bc, c ]

Algorithm

Using Recursion

Arguments passed in Power set function are:

• S: Given input String
• Size: Length of string S
• pos: Index in current permutation
• sset: Stores current Permutation Subset

Begin power-set

• power-set function is having four arguments given input string 'S', size of S, current position "pos", and subset string "sset" which will stores subset.
• Base condition: if current pos is equal to the size of given string S then return.
• print the subset string.
• Run a for-loop for i: current pos +1 to size of give string.
  • concatenate the element of S[i] into subset string(sset).
  • Now call the power-set function by giving S, size, i+1, sset
  • remove one element from the last of sset.
• return
  End power-set

Using Recursion method
power-set(S, size, pos, sset){ 
        if(pos is equals to the size) 
        then 
            return 
        end if 
        
        print string sset 
        
        for i: pos + 1 to size 
            concatenate the element of S[i] into sset 
            power-set(S, size, i+1, sset) 
            remove one(1) elements from string sset from end 
        end for 
        return 
    }

Code

#include <bits/stdc++.h>
using namespace std;

//-----------Power-Set Function---------------//
void power_set(string S, int n, int pos = -1, string sset = "") {
    //Base case condition
    if (pos == n)
        return;

    //Print string in Subset
    cout<<sset<<"\n";
    for (int i = pos + 1; i < n; i++) {
        sset+= S[i];

        power_set(S, n, i, sset);

        //BackTracking
        sset = sset.erase(sset.size() - 1);
    }
    return;
}

//----------Remove Duplicate Elements--------//
string duplicate(string s){
    if(s.size()==0){
        return "";
    }


    string x="";
    int n=s.size(),i=0;
    x+=s[0];
    for(int j=1;j<n;j++){
        if(x[i]!=s[j]){
            i++;
            x+=s[j];
        }
    }
    return x;
}

//-----------Driver Function---------------//
int main() {
    string S;

    cout<<"Enter string: \n";
    cin>>S;

    cout<<"Power Set of the string '"<<S<<"' is :\n";
    //sort the elements
    sort(S.begin(),S.end());
    //call duplicate() to remove duplicate elements
    S=duplicate(S);
    //calling power-set function
    power_set(S, S.size());

    return 0;
}

Output

Enter string:
merge
Power Set of the string 'merge' is :

e
eg
egm
egmr
egr
em
emr
er
g
gm
gmr
gr
m
mr
r

Using Iteration

Keep some logical things in mind, given below:

• '&'(Bitwise And) works as it takes two operands and does And on every bit of two numbers.
  Example: Take operand-1 as 2: 010(in binary) and operand-2 as 6: 110(in binary). Now, take these two operands and do bitwise and operation i.e. (110)&(010)= 10 (in decimal it is '2').
• '<<'(Bitwise left shift) works as it shifts the bit of first operand the specified number of bits.
  Example: if x=2(10 in binary), then y = x<<2 = 8(1000 in binary).

Begin power-set(s)

• Where s: given string
• take variable to store elements of power set, lets say sub
• for i: 0 to 2^(length of s)
  • take a string variable to store current permutation subset, lets say sset
  • for j:0 to (length of s)
    • condition: if(jth bit of i is set"1"), then insert the element on s[j] into sset
  • insert the sset into sub
• sort the elements of sub
• Now print all the elements of sub
  End power-set

power-set(s, length)
        take a variable which will store all the string of power set, say sub 
        take a variable, lets say power, which will run up 2^length
        
        for i:0 to power
            take a string variable say sset to store current permutation subset
            for j:0 to length 
                condition: if(i & (1<<j))
                             then insert s[j] into sset
             end for
             
             insert the sset into sub 
         end for
         
         sort the sub
         
         print the elements of sub using loop 
         return

Where s: given input string
length: size of String s

Code

#include <bits/stdc++.h>
using namespace std;

//-----------Power-Set Function---------------//
void power_set(string s,int n) {
    vector<string> sub;
    int power;

    power=pow(2,n);
    for(int i=0;i<power;i++){
        string sset="";

        for(int j=0;j<n;j++){
            if(i & (1<<j)){
                sset+=s[j];
            }
        }

        //push the subsequence into sub
        sub.push_back(sset);
    }

    //sort the vector string
    sort(sub.begin(),sub.end());

    //print the Power-set
    int len=sub.size();
    for(int i=0;i<len;i++){
        cout<<sub[i]<<endl;
    }

    return;
}

//----------Remove Duplicate Elements--------//
string duplicate(string s){
    if(s.size()==0){
        return "";
    }


    string x="";
    int n=s.size(),i=0;
    x+=s[0];
    for(int j=1;j<n;j++){
        if(x[i]!=s[j]){
            i++;
            x+=s[j];
        }
    }
    return x;
}

//-----------Driver Function---------------//
int main() {
    string S;

    cout<<"Enter string: \n";
    cin>>S;

    cout<<"Power Set of the string '"<<S<<"' is :\n";
    //sort the elements
    sort(S.begin(),S.end());
    //call duplicate() to remove duplicate elements
    S=duplicate(S);
    //calling power-set function
    power_set(S, S.size());

    return 0;
}

OUTPUT

Enter string:
algo
Power Set of the string 'algo' is :

a
ag
agl
aglo
ago
al
alo
ao
g
gl
glo
go
l
lo
o

Complexity

Using Recursion

Time Complexity: O(N*(2^N)), N is the size of the given input string and 2^N elements in power-set.
Space Complexity: O(N), N is the size of string.
In the worst case scenario, the depth of the recursion tree would be ‘N’. Hence, the overall space complexity due to the recursion call stack is O(N).

Using Iterartion

Time Complexity: O(N*(2^N)), N is the size of the given input string and 2^N elements in power-set.
Space Complexity: O(1), constant space complexity.