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.

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