0
Go4Expert Member
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.
0
Go4Expert Founder
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 numbervoid 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.
0
Go4Expert Member
Hats off to you shabbir ! I cant belive you figured this out so soon. You are a true algo expert !
Thanks
0
Newbie Member
thanks alot dear
0
Go4Expert Founder
My pleasure.
0
Go4Expert Member
thanks.....nice one.

Last edited by shabbir; 14Nov2006 at 18:18.. Reason: Confine links to signatures only
0
Go4Expert Founder