Description: Write a C program to print all permutations of a given string.

 
If video does not load, Click here
 
Example:

Eg: MAN

Output:

MAN

MNA

AMN

ANM

NAM

NMA

Algorithm and Implementation:

There are n! different permutations possible for a given string of length ā€˜nā€™. If the first element is fixed, there are (n-1)! different permutations possible. The first element can be fixed in ā€˜nā€™ ways.

 

Here is a solution using backtracking:

# include <stdio.h>

/*function used to swap values*/

void swap (char *x, char *y)

{

            char temp;

            temp = *x;

            *x = *y;

            *y = temp;

}

 

/*The following function prints the required permutations*/

void permute(char *string, int i, int end)

{

   int j;

   if (i == end)

            printf("%s\n", string);

   else

   {

            for (j = i; j <= end; j++)

            {

            swap((string+i), (string+j));

            permute(string, i+1, end);

            swap((string+i), (string+j)); /*backtrack*/

            }

   }

}

 

/* Driver program to test above functions */

int main()

{

   char string[] = "MAN";

   int start=0;//starting index

   int end=2;//end index

   permute(string, start, end);

   printf("\n");

   return 0;

}

 

Time Complexity:

O(n*n!)

Go to top