Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/articles/cpp-tutorials/)
-   -   All possible combinations of a string (http://www.go4expert.com/articles/combinations-string-t227/)

anjanesh 27Dec2004 17:17

All possible combinations of a string
 
All possible combinations of a string
1. Finds all possible cominations of a given string. The total number of combinations with recurrences is the factorial of the string length.
2. Have given the word 'post' as an example since if I included a cin >> word; then a user may unconscientiously enter a long word which will take toooo long to end. To change to another word change the string str.
3. A 9 letter word like 'aeroplane' can take around 40 seconds on a 1GHz machine. A 10 letter word will take 9 x 40 s - thats 6 mins! So watch out for the string length.
4. This may time according to the length of the string str

Code: CPP

// Combination

#include<iostream.h>
#include<string.h>
#include<conio.h>

unsigned long fact(unsigned long); // finds factorial of a number
void swap(int[],int,int);
void display(int[],char[]);
void Add(int[],int);

void main()
{
    // clrscr(); // Remove the first comment tag if running in TC++ or BC++ DOS mode
    int j,k,n;
   
    unsigned long i;
    char str[]="post"; // small word
    n=strlen(str);
    int*key=new int[n+1];
    key[0]=n; // key[0] contains the total no: of letters
    for (i=1;i<=key[0];i++)
        key[i]=i;
    display(key,str);
    swap(key,key[0],key[0]-1);
    display(key,str);
    for (i=3;i<=fact(key[0]);i+=2)
    {
        for (j=key[0]-1;j>=0;j--)
        {
            if ((i-1)%fact(j)==0)
            {
                Add(key,key[0]-j);
                for (k=1;k<=key[0]-j-1;k++)
                    if (key[k]==key[key[0]-j])
                    {Add(key,key[0]-j);k=0;}
            }
        }
        display(key,str);
        swap(key,key[0],key[0]-1);
        display(key,str);
    }
    cout << "\nTotal no: of combinations = " << key[0] << "! = " << i-1;
    getch();
}

unsigned long fact(unsigned long f)
{
    return f==0?1:f*fact(f-1);
}

void swap(int k[],int a,int b)
{
    int t=k[a];k[a]=k[b];k[b]=t;
}

void display(int k[],char s[])
{
    for(int i=1;i<=k[0];i++)
        cout << s[k[i]-1];
    cout << '\t';
}

void Add(int k[],int i)
{
    k[i]++;
    if (k[i]==k[0]+1)
        k[i]=1;
}


shabbir 27Dec2004 18:14

Re: All possible combinations of a string
 
First of all welcome to the go4expert forums and yes a nice code also.

Can you mention which compiler it will compile as its not meant for Visual Studio as it has clrscr method.

Thanks
Shabbir Bhimani

anjanesh 28Dec2004 18:25

Re: All possible combinations of a string
 
I wrote this using TC++ 3.1.
It compiled and worked in TC++ 3.1 and Borland C++ 3.11.
Remove clrscr() and it compiles and executes in vc++6 - checked.

shabbir 28Dec2004 18:43

Re: All possible combinations of a string
 
Thats nice.

sanjit_Developer 30Dec2004 10:56

Re: All possible combinations of a string
 
Hi,
Thats an extraordinary contribution frnd.Thanx.
sanjit khasnois

jcnovoa 11Oct2005 21:13

Re: All possible combinations of a string
 
Thank you... with a little modification, I was able to make it work for my C# app that I am working on. Great code... too bad google ranks it so low in its engine

shabbir 11Oct2005 23:03

Re: All possible combinations of a string
 
Quote:

Originally Posted by jcnovoa
too bad google ranks it so low in its engine

Google is slowly loosing the share and the quality in Search domain. In sitepoint forum in some thread I read recently that within couple of years Google has lost from 90% of the share traffic to 48% and the rest have moved to Yahoo and MSN. Its probably because they are more interested in satisfying there Clients of adwords.

Alaj 20Jul2006 14:09

Re: All possible combinations of a string
 
hello
this is realy a very good code ...

can any one tell me that what is the basic process of function

void add (int[] , int);

i need its processing flow plz if anybody can help me i'll be thankful

anjanesh 20Jul2006 15:01

Re: All possible combinations of a string
 
I should've documented this when I wrote this in college 4 yrs back.
I'll try to remember and repost this code with documentation.

Alaj 21Jul2006 10:45

Re: All possible combinations of a string
 
hello
one more question is that plz tell me the logic of "if ((i-1)%fact(j)==0)" this condition in this code..
and plz send that documentation as soon as possible

anjanesh 21Jul2006 10:52

Re: All possible combinations of a string
 
I spent a lot of time try to get this algo in college days. But never bothered to write down the steps.
I'll defintely post the documentation here in a few weeks time after I recollect the steps.

shabbir 21Jul2006 15:21

Re: All possible combinations of a string
 
I have documented the code completely
Code: CPP

// Combination

#include<iostream.h>
#include<string.h>
#include<conio.h>

unsigned long fact(unsigned long); // finds factorial of a number
void swap(int[],int,int);
void display(int[],char[]);
void Add(int[],int);


/***********************************************************************/
/// <b>Function: main</b>
///
/// \param   NONE
///
/// \return void
///
/// \remarks    main function
///
/***********************************************************************/
void main()
{
    int j,k,n;
    unsigned long i;

    char str[]="G4EF"; // sample small word

    n=strlen(str); // Get the length of the string

    int*key=new int[n+1]; // Allocate buffer of size n+1

    key[0]=n; // key[0] contains the total no: of letters

    // Assign all the keys an index from the string
    for (i=1;i<=key[0];i++)
        key[i]=i;

    display(key,str); // Displays the string
   
    swap(key,key[0],key[0]-1); // swaps the key values n and n-1
   
    display(key,str); // Displays the string
   
    // Added by Shabbir
    // store the factorial once and so it does not calulate each time
    unsigned long num = fact(key[0]);

    // Loop till factorial n so we get all the combination of strings
    // It starts with i=3 as we already have 2 combination
    // Its increments by 2 as we get 2 combination with the help of swap
    for (i=3;i<=num;i+=2)
    {
        // Loop for all the elements of the string
        for (j=key[0]-1;j>=0;j--)
        {
            // Edited by Shabbir
            // Can be avoided
            //if ((i-1)%fact(j)==0)
            {
                Add(key,key[0]-j)// Increment the key in a cyclic form
                for (k=1;k<=key[0]-j-1;k++)
                {
                    // If kth index in key is euqal to n-jth index
                    if (key[k]==key[key[0]-j])
                    {
                        Add(key,key[0]-j); // Increment the key in a cyclic form
                        k=0;
                    }
                }
            }
        }
        display(key,str); // Displays the string
        swap(key,key[0],key[0]-1); // swaps the key values
        display(key,str); // Displays the string
    }
    cout << "\nTotal no: of combinations = " << key[0] << "! = " << i-1;
    cout<<endl;
    getch();
}


/***********************************************************************/
/// <b>Function: fact</b>
///
/// \param  long f    (in)
///
/// \return unsigned long
///
/// \remarks    returns the factorial of parameter f using recursion
///
/***********************************************************************/
unsigned long fact(unsigned long f)
{
    return f==0?1:f*fact(f-1);
}


/***********************************************************************/
/// <b>Function: swap</b>
///
/// \param  k[]   (out)
///
/// \param  a (in)
///
/// \param  b (in)
///
/// \return void
///
/// \remarks    Swaps the index of the key.
///
/***********************************************************************/
void swap(int k[],int a,int b)
{
    int t=k[a];k[a]=k[b];k[b]=t;
}


/***********************************************************************/
/// <b>Function: display</b>
///
/// \param  k[]   (in)
///
/// \param  s[]   (in)
///
/// \return void
///
/// \remarks    Displays the string using the key
///
/***********************************************************************/
void display(int k[],char s[])
{
    for(int i=1;i<=k[0];i++)
        cout << s[k[i]-1];
    cout << '\t';
}


/***********************************************************************/
/// <b>Function: Add</b>
///
/// \param  k[]   (out)
///
/// \param  i (in)
///
/// \return void
///
/// \remarks    Increments the key values of the index i. If it crosses
///    the max limit resets back to 1. i.e. in cyclic form.
///
/***********************************************************************/
void Add(int k[],int i)
{
    k[i]++;
    if (k[i]==k[0]+1)
        k[i]=1;
}

Also I have removed some unnecessary calculations which now speeds up the process. I have added "Added/Edited by shabbir" so that its easily trackable.

anjanesh 21Jul2006 22:45

Re: All possible combinations of a string
 
Hats off to you shabbir ! I cant belive you figured this out so soon. You are a true algo expert !
Thanks

Alaj 21Jul2006 23:19

Re: All possible combinations of a string
 
thanks alot dear

shabbir 22Jul2006 19:14

Re: All possible combinations of a string
 
My pleasure.

BlasterBlang 14Nov2006 17:47

Re: All possible combinations of a string
 
thanks.....nice one.

shabbir 14Nov2006 18:18

Re: All possible combinations of a string
 
BlasterBlang, Please confine links to signature only.

BlasterBlang 17Nov2006 16:42

Re: All possible combinations of a string
 
ok fine

aisha.ansari84 5Mar2008 18:45

Re: All possible combinations of a string
 
nice code

rahul.mca2001 6Mar2008 13:22

Re: All possible combinations of a string
 
there is no speed problem in the code now

radams 7May2008 01:22

Re: All possible combinations of a string
 
Hate to tell you this but this code doesn't generate all possible combinations. Upon testing the code and converting it for java I have discovered that is duplicates combinations. I put in the word "abcd" and it generates the same "abcd" twice. It seems to work fine for 3 letter words. There is clearly a bug in the code.


All times are GMT +5.5. The time now is 21:00.