Permutations of a String

Given a string, print all its permutations. 

Permutations of a string are all of the same length. All permutations have the same set of characters, but they in different order.

Solution:

Approach:
Let us say the given string is ABCD. Then, the number of possible permutations of this string
= 4!
= 4.3.2.1
= 24

ABCD        BACD        CBAD        DBCA
ABDC        BADC        CBDA        DBAC
ACBD        BCAD        CABD        DCBA
ACDB        BCDA        CADB        DCAB
ADCB        BDCA        CDAB        DACB
ADBC        BDAC        CDBA        DABC

There are 4 characters in the string "ABCD".
Let str[] = ['A', 'B', 'C', 'D'];
str[0] = 'A'
str[1] = 'B'
str[2] = 'C'
str[3] = 'D'

So, the first character can be any of the 4 letters.

Case 1: str[0] is 1st character.(i.e., we fix first character to be A)
So we need to arrange B, C, D at 2nd, 3rd and 4th places.
A_ _ _
        Case 1.1: B occupies 2nd spot.
        AB_ _
        Case 1.2: C occupies 2nd spot.
        AC_ _
        Case 1.3: D occupies 2nd spot.
        AD_ _

Case 2: str[1] is 1st character.(i.e., we fix first character to be B)
So we need to arrange A, C, D at 2nd, 3rd and 4th places.
B_ _ _
        Case 2.1: A occupies 2nd spot.
        BA_ _
        Case 2.2: C occupies 2nd spot.
        BC_ _
        Case 2.3: D occupies 2nd spot.
        BD_ _
Case 3: str[2] is 1st character.(i.e., we fix first character to be C)
So we need to arrange A, B, D at 2nd, 3rd and 4th places.
C_ _ _
        Case 3.1: A occupies 2nd spot.
        CA_ _
        Case 3.2: B occupies 2nd spot.
        CB_ _
        Case 3.3: D occupies 2nd spot.
        CD_ _

Case 4: str[3] is 1st character.(i.e., we fix first character to be D)
So we need to arrange A, B, C at 2nd, 3rd and 4th places.
D_ _ _
        Case 4.1: A occupies 2nd spot.
        DA_ _
        Case 4.2: B occupies 2nd spot.
        DB_ _
        Case 4.3: C occupies 2nd spot.
        DC_ _


So, in this recursive approach each time we fix the 1st character, and call the same Permute function on the rest of the string. When we reach the end of the string, we print it.

In this way, a recursion tree is formed. We start from root (in this case, "ABCD"), and recursively traverse down the tree. We print all the leaves of the recursion tree.
Number of leaves in the recursion tree = Number of permutations of the input string.


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

At each stage of the permutation process, the given set of elements consists of two parts: a subset of values that already have been processed, and a subset that still needs to be processed. This logical separation can be physically realized by exchanging, in the i’th step, the i’th value with the value being chosen at that stage. That approaches leaves the first subset in the first i locations of the outcome.

permute(i) 
   if i == N  output A[N] 
   else 
      for j = i to N do 
         swap(A[i], A[j]) 
         permute(i+1) 
         swap(A[i], A[j]) 

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

Implementation:

#include <stdio.h>

/*Auxiliary function to swap values of 2 pointers*/
void swap(char *x, char *y)
{
    char temp = *x;
    *x = *y;
    *y = temp;
}

/*Function to print the permutations of a string*/
void Permute(char *str, int index, int n)
{
    int i;
    if(index == n)
        printf("%s\n", str);
    else
    {
        for(i = index; i <= n; i++)
        {
            swap((str+index), (str+i)); 
            //same as swap(&str[index], &str[i])
            Permute(str, index+1, n);
            swap((str+index), (str+i));
        }
    }
}

int main()
{
    char s[] = "ABC";
    Permute(s, 0, 2);
    return 0;
}

Output:
ABC
ACB
BAC
BCA
CBA
CAB

Time Complexity: O(n!)