All Permutations

Given a string,the task is to print all the permutations of the string.
A permutation is a rearrangement of the elements of an ordered list S.A string of length N has N! permutations.

Example-

Let the string be S=”abc”.

Length of the string=3

Number of permutations=3!=6

Permutations-

abc
acb
bac
bca
cab
cba

Algorithm-

Basic idea-

All permutations of a string X is the same thing as all permutations of each possible character in X, combined with all permutations of the string X without that letter in it.

All permutations of “abcd” are-

“a” concatenated with all permutations of “bcd”.
“b” concatenated with all permutations of “acd”.
“c” concatenated with all permutations of “bad”.
“d” concatenated with all permutations of “bca”.

Recursive solution-

The first character is kept constant and permutations are generated with the rest.Then,the first two characters are kept constant and permutations are generated with the rest until we are out of characters.

This algorithm is performed on the input string itself.Thus,no additional memeory is required.The “backtracking” undoes the changes to the string, leaving it in its original state.

Code-



char a[1000];//string

//to swap characters at position i and j

void swap (int i, int j)
{
    char temp;
    temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

//i is the starting index 
//n is the ending index
//initially,permute(0,n-1) is called

void permute(int i, int n)
{
   int j;

   if (i == n)
     printf("%s\n", a);

   else
   {
        for (j = i; j <= n; j++)
       {
          swap(i,j);
//increasing the number of fixed characters
          permute(i+1, n);
          swap(i,j); //backtrack
       }
   }
} 

Note-

It has a time complexity of O(N*N!) and is an example of Backtracking.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

41,085 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>