Amazon Prime

  • Maths
  • Permutation


    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.


    Permutations of 3 Letters


    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
    3Step 0: Initialize start to 0 and end to n-1
    4 method : permutations(array, start, end)
    6Step 1: for index -> start to end
    8Step 2: fix position at index and swap character at start with index
    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) )
    12Step 4: Backtrack by swapping start with index

    Permutation Tree of 3 Letters

    Code Implementation

    1import java.util.Arrays;
    3public class Permutations {
    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 }
    11 private void permutation(char[] array, int start, int end) {
    12 if (start == end) {
    13 System.out.println(Arrays.toString(array));
    14 }
    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 }
    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 }

    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!)

  • Maths
  • Permutation