Permutations of a string using recursion

Updated roverphoenix 0 Tallied Votes 418 Views Share

A simple program to calculate permutations of a string using recursion, I have used a malloc string of size 100 , you can change it to whatever value you want.

The author is currently working at Microsoft,any questions can be directed to [email snipped]

#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]]);
    }
}
~s.o.s~ 2,560 Failure as a human Team Colleague Featured Poster

Using goto LABEL; is not a recommended programming practice. THe same applies to system ("PAUSE") calls. Calling OS dependent functions is not good programming practice.

unicell 0 Newbie Poster

seems a bit lenghy, here is my solution

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
void swap(char* src, char* dst)
{
        char ch = *dst;
        *dst = *src;
        *src = ch;
}
/* permute [set[begin], set[end]) */
int permute(char* set, int begin, int end)
{
        int i;
        int range = end - begin;
        if (range == 1) {
                printf("set: %s\n", set);
        } else {
                for(i=0; i<range; i++) {
                        swap(&set[begin], &set[begin+i]);
                        permute(set, begin+1, end);
                        swap(&set[begin], &set[begin+i]);       /* set back */
                }
        }
        return 0;
}
int main()
{
        char str[] = "abcd";
        permute(str, 0, strlen(str));
        return 0;
}
challarao 0 Junior Poster in Training

A simple program to calculate permutations of a string using recursion, I have used a malloc string of size 100 , you can change it to whatever value you want.

The author is currently working at Microsoft,any questions can be directed to raghu_tillu@hotmail.com

It takes very long time to complete the task,may be because of the spaces,1 hour is also not sufficient for completion of 14 char string.

roverphoenix 0 Newbie Poster

It takes very long time to complete the task,may be because of the spaces,1 hour is also not sufficient for completion of 14 char string.

feel free to edit or modify the code, its been a long time since I have played around with this code :)

WaltP 2,905 Posting Sage w/ dash of thyme Team Colleague

feel free to edit or modify the code, its been a long time since I have played around with this code :)

Then you should have played with it before posting. goto and gets() are extremely poor techniques in coding. And for a professional? At M$? No wonder updates are needed continuously...

roverphoenix 0 Newbie Poster

hey waltp that code was written by me when I was in high school moron, I just mentioned Iam working in mS$ doesnt mean I wrote it now and where do you work in ? chop shop in china?

WaltP 2,905 Posting Sage w/ dash of thyme Team Colleague

And where do you state you were in HS? You're the one that mentioned "the author is currently working at Microsoft" with no timeline, explanation, etc. to let us know you wrote it years before.

Who's the moron now? Maybe you should have left a 5-year-old thread stay buried.

roverphoenix 0 Newbie Poster

and what's pricking you if I state that I work in MS, sour grapes ? got laid off or what..

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.