// 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;
}