Permutations of a string using recursion

Updated roverphoenix 0 Tallied Votes 440 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]]);
    }
}

Dani AI

Generated

This thread shows two common ways to generate permutations and the practical problems that come with them. ’s index/stack technique works, but it’s fairly intricate and easy to get wrong; ’s in‑place swap/backtracking approach is simpler to reason about and avoids an auxiliary index array. For clarity and maintainability prefer an in‑place algorithm (swap/restore) or a well‑known iterative method such as Heap’s algorithm — both produce each permutation without building large extra structures.

Safety and style notes raised by and are important. Avoid unsafe input routines and opaque control flow. Allocate exactly strlen(s)+1, check returns from malloc/calloc, free memory, and use a bounded input routine like fgets. Replace goto-style control with clear returns or error paths so the flow is easier to audit.

Performance and duplicates are the usual gotchas (see ’s timing comment). Factorial growth explodes quickly: 8! = 40,320; 10! = 3,628,800; 12! = 479,001,600; 14! ≈ 87,178,291,200 — printing all permutations for n≥12 is usually impractical. To handle repeated characters, either sort the input and skip identical choices at each recursion level, or use a used[] boolean array to avoid selecting the same position twice. If you don’t need every permutation, consider sampling or stopping early; in C++ std::next_permutation iterates lexicographically if that fits your use case.

Quick practical checklist: validate input length, pick an algorithm (swap/backtrack or Heap’s), handle duplicates up front, stream results to a file instead of storing them, compile with optimizations, and test with small n first. These steps keep the implementation correct, safer, and far easier to profile and scale.

~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

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.