Write a c program for printing all permutation of a string is a good problem to learn recursive backtracking algorithm.Let us consider a string “abcd“. Then permutation of abc will be abcd, acbd, bacd, bcad, cbad, cabd.

The permutation is all different arrangements of a given sequence but how can we generate all permutation? 

A permutation can be obtained by selecting an element in the given set and recursively permuting the remaining elements.

Write a c program for printing all permutation of a string

#include <stdio.h>
#include <string.h>
 
void swap(char *p, char *q)
{
    char temp;
    temp = *p;
    *p = *q;
    *q = temp;
}
 
void permute(char *a, int i, int length)
{
   int j;
   if (i == length)
   {
     for(int x=0; x <= length; x++)
       printf("%c ", a[x]);
     printf("\n");
   }
   else
   {
       for (j = i; j <= length; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, length);
          swap((a+i), (a+j)); //backtrack
       }
   }
}
 
int main()
{
    char a[] = "abcd";
    int n = strlen(a);
    permute(a, 0, n-1);
    return 0;
}

The output is

abcd
acbd
bacd
bcad
cbad
cabd

The above program will print all permutation with repetition. The above program  needs to be modified for permutation of a string without repetition.

Reference:

http://web.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html



Related Contents to follow