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