What is Permutation

Permutation is an arrangement of objects into a sequence or linear order. To understand permutations more clearly, let’s understand with a small use case that, if you have a locker and you are given 3 letters a, b and c construct a key to unlock the locker. It is given that the key is of length 3 and it contains all letters a, b and c. So we need to try all permutations to construct key to unlock the locker :

abc, acb, bac, bca, cab, cba

From these permutations, one of them is the key to unlock the locker.

How many permutations ?

For 1 letter a, only one order is possible which a, so the number of permutations is 1.

For 2 letters a,b we can arrange them a, b and b, a. So the number of permutations is 2.

For 3 letters a, b and c, we can arrange them in abc, acb, bac, bca, cab, cba. So the number of permutations is 6.

Algorithm

Permutation of given letters is formed by interchanging the position of the letters. To do this we can use backtracking algorithm. The idea is to fix position and swap the element at the position with remaining elements.

1Input : char array of length n, and n = 3 
2
3Step 0: Initialize start to 0 and end to n-1
4        method : permutations(array, start, end) 
5
6Step 1: for index -> start to end  
7
8Step 2: fix position at index and swap character at start with index  
9
10Step 3: Now recursively construct all other possible permutation for the rest of the positions ( by calling the same method for start+1 , i.e, permutation(array, start+1, n) )
11
12Step 4: Backtrack by swapping start with index 

Code Implementation

1import java.util.Arrays;
2 
3public class Permutations {
4 
5    public static void main(String[] args) {
6        Permutations obj = new Permutations();
7        char[] array = {'a', 'b', 'c'};
8        obj.permutation(array, 0, array.length-1);
9    }
10 
11    private void permutation(char[] array, int start, int end) {
12        if (start == end) {
13            System.out.println(Arrays.toString(array));
14        }
15
16        for (int i=start; i<= end; i++){
17            array = swap(array, start, i);
18            permutation(array, start+1, end);
19            array = swap(array, start, i);
20        }
21    }
22 
23    private char[] swap(char[] a, int i, int j) {
24        char temp = a[i];
25        a[i] = a[j];
26        a[j] = temp;
27        return a;
28    }
29}

1Output : 
2[a, b, c] 
3[a, c, b] 
4[b, a, c] 
5[b, c, a] 
6[c, b, a] 
7[c, a, b] 

Complexity Analysis

• Time Complexity : O(n * n!)
• Space Complexity : O(n!)