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;                }            }        }    }}`