Algorithm to print all combination of letters of the given string in lexicographical order

sac picture sac · Mar 15, 2015 · Viewed 11.9k times · Source

I tried to create the code to generate all possible combination of the given string in the lexicographical order:

The code that I wrote is:

void get(char *n)
 {
    int l=strlen(n); 
    sort(n,n+l);
    int k=0,m,i,j,z;

    while(k<l)
    {
        m=k;

        for(i=k;i<l;i++)
        {
            for(j=k;j<=i;j++)
                cout<<n[j];

            cout<<"\n";
        }

        for(z=m+2;z<l;z++)
            cout<<n[m]<<n[z]<<"\n";  

        k++;
    }
 }


int main() 
 {
    char n[100];
    cin>>n;
    get(n);
    return 0;
 }

Suppose the string is : abcde

My code is not generating combinations like:

abd
abe

The output I am getting for the string abcde are:

a 
ab
abc 
abcd 
abcde 
ac 
ad
ae 
b 
bc 
bcd 
bcde 
bd 
be 
c 
cd 
cde 
ce 
d 
de 
e

My output does not contains strings like : abd abe

Hope this makes the question clear

How to generate all these combinations using an efficient algorithm

Answer

user0815 picture user0815 · Mar 15, 2015

This is a simple recursive approach:

#include <string>
#include <iostream>
using namespace std;

void get( string str, string res ) {

   cout << res << endl;

   for( int i = 0; i < str.length(); i++ )
      get( string(str).erase(i,1), res + str[i] );
}

int main( int argc, char **argv) {

   string str = "abcde";
   get( str, "" );  
   return 0;
}

Maybe not the most efficient way of doing it, but a short and simple one. Keep in mind, that enumerating all combinations has a complexity of O(2n) anyway. So there exists no efficient algorithm at all.