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 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


All times are GMT +5.5. The time now is 11:59.