1,105,281 Community Members

Permutations of a string using recursion

Member Avatar
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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]]);
    }
}
Member Avatar
~s.o.s~
Failure as a human
10,399 posts since Jun 2006
Reputation Points: 2,496 [?]
Q&As Helped to Solve: 992 [?]
Skill Endorsements: 72 [?]
Administrator
Featured
 
0
 

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.

Member Avatar
unicell
Newbie Poster
1 post since Sep 2006
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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;
}
Member Avatar
challarao
Junior Poster in Training
67 posts since Aug 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 1 [?]
Skill Endorsements: 0 [?]
 
0
 

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.

Member Avatar
roverphoenix
Newbie Poster
13 posts since Sep 2005
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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

Member Avatar
WaltP
Posting Sage w/ dash of thyme
9,363 posts since May 2006
Reputation Points: 2,905 [?]
Q&As Helped to Solve: 1,151 [?]
Skill Endorsements: 45 [?]
Team Colleague
 
2
 

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

Member Avatar
roverphoenix
Newbie Poster
13 posts since Sep 2005
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
-1
 

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?

Member Avatar
WaltP
Posting Sage w/ dash of thyme
9,363 posts since May 2006
Reputation Points: 2,905 [?]
Q&As Helped to Solve: 1,151 [?]
Skill Endorsements: 45 [?]
Team Colleague
 
1
 

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.

Member Avatar
roverphoenix
Newbie Poster
13 posts since Sep 2005
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
-1
 

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

You
Post:
Start New Discussion
Tags Related to this Article