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.

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;

}

}

}

}

}