#include <stdio.h>
#include <stdlib.h>

void ComputePermutations(char string[]);

void Permutations(char string[],int stringLength, int level,int stack[]);

void IncrementAndAdjust(int level,int stack[],int stringLength,char string[]);

void DisplayStack(int stack[],int stringLength,char string[]);


int main(int argc, char *argv[])
{
    char *string;
    printf("\nEnter the string ..\n");
    string = (char *)malloc(100 * sizeof(char));
    if(!string)
    {
        printf("\nmemory allocation for string failed exiting ..\n");
        exit(0);                              
    }            
    gets(string);
    printf("\n\nPermutations..\n");
    ComputePermutations(string);
    return 0;
}

void ComputePermutations(char string[])
{
    int stringLength = 0;
    int *stack;
    int index = 0;

    stringLength = strlen(string); 
    stack = (int *)calloc(stringLength,sizeof(int));
    if(!stack)
    {
        printf("\nmemory allocation for stack failed exiting ..\n");
        goto EXIT;                              
    }
    for(index = 0; index < stringLength;index++)
    {
        stack[0] = index;
        Permutations(string,stringLength,0,stack);
    }

EXIT:
    return;     
}

void Permutations(char string[],int stringLength, int level,int stack[])
{
    int i = 0;
    
    if(level == stringLength - 1)
    {
        DisplayStack(stack,stringLength,string);
    }
    level++;
    for(i = 0;i < (stringLength - level);i++)
    {
        IncrementAndAdjust(level,stack,stringLength,string);
        Permutations(string,stringLength,level,stack);
    }
    printf("\n");
}

void IncrementAndAdjust(int level,int stack[],int stringLength,char string[])
{
    int index = 0;

    //increment the value of the level by 1
    stack[level] += 1;
    if(stack[level] >= stringLength)
    {
        stack[level] = stack[level] % stringLength;
    }
    // make sure the incremented value is not same as in the stack levels above it
    for(index = 0; index < level;index++)
    {   if(stack[level] == stack[index]) // a level above the current one has a similar value
        {
            stack[level] += 1;
            if(stack[level] >= stringLength)
            {
                stack[level] = stack[level] % stringLength;
            }
            index = -1;
        }        
    }
    //stack[level] is appropriately set
}

void DisplayStack(int stack[],int stringLength,char string[])
{
    int index = 0;
    for(index = 0; index < stringLength;index++)
    {
        printf(" %c ",string[stack[index]]);
    }
}