Tuesday, July 30, 2013

Program to generate all permutations of a given string

This is one of the famous programming problems. In this post, we discuss an algorithm to generate all permutations of a given array and how to implement the same in Java.This is also one of the beautiful example to understand recursion.

We discuss a recursive algorithm as it is simple to understand and implement. Let us define this problem in terms of itself. This is the first step in the process of forming a recursive solution.

Let us consider an array of length n. We can fix the first element (Observe that there are n possible ways) and try to generate permutations with the remaining (n-1) elements. Generating permutations of (n-1) elements is again the original problem, only with the smaller input size. Hence we can easily design  a recursive algorithm.

Here is how the algorithm works. Let us fix array[0] as the first element, and recursively find permutations for the remaining (n-1) elements. Next we will swap array[0] with array[1], and call the same function recursively for (n-1) elements and so on... for others( array[2], array[3],... array[n-1]). After every recursive call, we swap back the elements so that the original order is restored.

Let us understand this with a small example. The following is the recursion tree for a simple input array [1,2,3]. The elements marked in Red are the elements that are swapped.



Here is the Java implementation of the algorithm.


import java.util.Scanner;
public class Permutation {
    public static void main(String[] args)
    {
        Scanner reader = new Scanner(System.in);
        String input = reader.nextLine();
        printPermutations(input.toCharArray(),0);
    }
    public static void printPermutations(char[] input,int start)
    {
        //Base case for recursion, if start index is the end;
        //no need to recurse further, just print the pattern
        if( start == input.length-1 )
        {
            for(int i = 0; i < input.length; i++)
                System.out.print(input[i]);
            System.out.println();
        }
        else
        {
            //fix the first character and generate per
            for( int i = start; i < input.length; i++)
            {
                //swap start element, with ith element
                if( i!= start) // swap only if start, and i are different
                {
                    char t = input[start];
                    input[start] = input[i];
                    input[i] = t;
                }

                printPermutations(input,start+1);
                //swap back the elements
                if( i != start)
                {
                    char t = input[start];
                    input[start] = input[i];
                    input[i] = t;
                }
            }
        }
    }
}