Permutations

Raksha Jain
Last Updated: May 13, 2022

Introduction-

 

Today, let’s learn about a famous and commonly asked Interview Problem, i.e., all the possible permutations of the distinct integers in a given array.

It is a famous and common problem that is solved using dp in its most optimized version.  

 

Problem Statement: 

Given an array nums of distinct integers, return all possible permutations in any order.

 

Examples: 

Let the given array be [2, 3 ,5, 6]

All the possible permutations here are : 

[3, 2, 5, 6] [3, 2, 6, 5] [3, 5, 2, 6] [3, 5, 6, 2] [3, 6, 5, 2] [3, 6, 2, 5] [2, 3, 5, 6] [2, 3, 6, 5]

[2, 5, 3, 6] [2, 5, 6, 3] [2, 6, 5, 3] [2, 6, 3, 5] [5, 2, 3, 6] [5, 2, 6, 3] [5, 3, 2, 6] [5, 3, 6, 2]

[5, 6, 3, 2] [5, 6, 2, 3] [6, 2, 5, 3] [6, 2, 3, 5] [6, 5, 2, 3] [6, 5, 3, 2] [6, 3, 5, 2] [6, 3, 2, 5]

 

Now, let's get started and learn various approaches to solve this problem. 

 

Approach - Using Backtracking

 

We could find all the possible permutations of the distinct integers in a given array via simply:

  1. Swapping all the integers with the i-th index
  2. Calculating all the permutations for (i + 1)th index
  3. Backtracking or re-swapping i-th index with the previously swapped integer in (1).

 

Once, our i-th index reaches the last index of the array, this means all the swappings have been performed for that particular swap (of original 0th index with rest of the integers), and an answer has been generated. So, we store this answer which is in the form of arraylist to our array of arraylist and finally return it. 

Note: This is our base case as well.

 

Implementation-

Let’s have a look at its implementation in Java -

 

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        Scanner s = new Scanner(System.in);
 
        System.out.println("Enter size of array ");
        int n = s.nextInt();
        int[] nums = new int[n];
 
        System.out.println("Enter integers in array");
        for (int i = 0; i < n; i++) {
            nums[i] = s.nextInt();
        }
        
        List<List<Integer>> list = new ArrayList<>();
        list = permute(nums);
        
        System.out.println("Possible permutations are: ");
        for (int i = 0; i < list.size(); i++){
            System.out.println(list.get(i));
        }
    }
    
    public static List<List<Integer>> permute(int[] nums) {
        
        // Forming arraylist for storing a particular permutation
        List<List<Integer>> arrLL = new ArrayList<>();
        
        // Adding all nums in arrayList
        ArrayList<Integer> arrtemp = new ArrayList<>();
        for (int i : nums) {
            arrtemp.add(i);
        }
        
        // Calling the function
        permutations(arrtemp,0, arrLL);
        return arrLL;
    }
    
    // Solving via Backtracking
    public static void permutations(ArrayList<Integer> arrtemp, int idx, List<List<Integer>> arrLL){
        
        // Base Case
        if (idx == arrtemp.size()){
            arrLL.add(new ArrayList<Integer> (arrtemp));    
            return;
        }
        
        
        // Swapping with right side of idx
        for (int i = idx; i < arrtemp.size(); i++){    
            swap(arrtemp, i, idx);
            permutations(arrtemp, idx + 1, arrLL);
            swap(arrtemp, i, idx); 
        }
    }
    
    public static void swap(ArrayList<Integer> arrtemp, int i, int idx){
        int temp = arrtemp.get(i);
        arrtemp.set(i, arrtemp.get(idx));
        arrtemp.set(idx, temp);
    }

}

 

Output:

 

Enter size of array 4

Enter integers in array 3 2 5 6

Possible permutations are: 

[3, 2, 5, 6]

[3, 2, 6, 5]

[3, 5, 2, 6]

[3, 5, 6, 2]

[3, 6, 5, 2]

[3, 6, 2, 5]

[2, 3, 5, 6]

[2, 3, 6, 5]

[2, 5, 3, 6]

[2, 5, 6, 3]

[2, 6, 5, 3]

[2, 6, 3, 5]

[5, 2, 3, 6]

[5, 2, 6, 3]

[5, 3, 2, 6]

[5, 3, 6, 2]

[5, 6, 3, 2]

[5, 6, 2, 3]

[6, 2, 5, 3]

[6, 2, 3, 5]

[6, 5, 2, 3]

[6, 5, 3, 2]

[6, 3, 5, 2]

[6, 3, 2, 5]

 

Time and Space Complexity-

 

Time Complexity: O(N!) as there are N integers in the given array of integers and the number of permutations that exist are N!. 

Note: Swapping takes O(1) time to swap integers in arraylist in java.  

 

Space Complexity: O(1) as no extra space is being used.

 

Frequently Asked Questions-

 

  1. What is a permutation?

Ans. A permutation is a collection of objects from a set where the order or the arrangement of the chosen objects does matter. So, is an arrangement of objects in a definite order. 

 

2. What is backtracking? How does it help in finding out our solution?

Ans.  Backtracking is an algorithmic-technique for solving problems recursively by building a solution incrementally - one piece at a time and removing those solutions that fail to satisfy the constraints of the problem at any point of time. So, it is a systematic way of trying out different sequences of decisions until we find one that "works."

 

3. What is the formula used to calculate permutation of integers in mathematics?

Ans. A permutation is the choice of ‘R’ things from a set of ‘N’ things without replacement and where the order matters. The formula used is: 

NPR = (N!) / (N-R)!

 

Key Takeaways-

  

In this blog, we learned various approaches to find all the possible permutations of the distinct integers in a given array.
 

  • A permutation is a collection of objects from a set where the order or the arrangement of the chosen objects does matter. So, is an arrangement of objects in a definite order. 
  • A permutation is the choice of ‘R’ things from a set of ‘N’ things without replacement and where the order matters. In mathematics, the formula used is: 

NPR = (N!) / (N-R)!

  • The optimized time complexity of this problem is O(N!) as there are N integers in the given array of integers and the number of permutations that exist are N!. 

 

Check out more blogs on different dp problems like LCS, Friends Pairing Problem to read more about these topics in detail. And if you liked this blog, share it with your friends!

Practice a variety of on CodeStudio  platform where you can find questions asked in all big-tech giants.

 

Was this article helpful ?
0 upvotes