Print all possible permutations of a given array without duplicates

Introduction

Hello Ninjas!! We are back with a new data structure problem, i.e., Print all possible permutations of a given array without duplicates. Here we will start with the problem statement, followed by the approach and the implementation in different languages.

Let's discuss the problem statement where your doubts about a permutation will get resolved.

Problem Statement

The problem states that we are given an array of integers, and we need to print all possible permutations of that array without repeating any of the permutations, even if there are duplicate characters in the given array. Let's discuss what a permutation is in brief. 

What is a Permutation?

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an array, arr into a one-to-one correspondence with arr itself. An array of length n has n! Permutation.

Let say we have arr[] = {1,2,3}

All possible permutation of the given array are :  

{3,1,2}, {3,2,1}, {1,2,3}, {1,3,2} , {2,1,3}, {2,3,1}.

There is a total of 6 permutations, i.e., 3!. 

Prerequisites

Basic knowledge of the backtracking algorithm is required for finding all possible permutations of an array. 

Sample Examples

Example 1:

Input: arr[] = {1,2,4}
Output: There are 6 possible permutations. 
1 2 4 
1 4 2 
2 1 4 
2 4 1 
4 1 2 
4 2 1 

Explanation: 
A permutation is explained above with an example also.

 

Example 2:

Input: arr[] = {1,4}
Output: There are 2 possible permutations. 
1 4 
4 1   
Explanation: Permutation is explained above with an example also.

Recommended: Before stepping into the solution, try it by yourself on CodeStudio.

Approach

To find all the permutations of an array, we will use the backtracking type of algorithm and save all possible permutations in the set data structure to remove the duplicates. 

Algorithm

  1. Make a vector nums that will store the current permutation.
  2. Make a set of vectors and push the vector nums into it. 
  3. At last, print the content of this set; this will give us all possible permutations of the given array without any duplicates. 

 

Let's make permutations of array [1,2,4]. In this case, we will keep the first index, 1, fixed and then try to make the permutations of the remaining elements. We will get: {1 2 4}, {1 4 2} 

Now, we have all the permutations by keeping the 1 fixed.  Now we will keep the 2, fixed at the first position and try to make the permutations. We will get: {2 1 4}, {2 4 1}.  

Similarly, keeping 4 at the first position, we will get: {4 1 2}, {4 2 1}.

So, finding the permutation of 1,2, and 4 was easy. Now we will keep the same logic and try to find the permutations of 1,2,3, and 4. 

We will first keep 1 fixed. Therefore we have now only 2, 3, and 4. 

So we will make the permutations of these numbers by keeping the 2 fixed, we will get:  {1 2 3 4},  {1 2 4 3}

Now, we will fix 3 from 2, 3 and 4, we will get:  {1 3 2 4}, {1 3 4 2}.

Again, keeping 4 fixed from 2,3 and 4, we will get : {1 4 2 3}, {1 4 3 2}.

 

Now, we have all the permutations when 1 is fixed.  Similarly, we will keep other digits fixed at first and obtain the remaining permutations. You can now notice that we are breaking the larger array into the smaller one. After obtaining permutations of the smaller size array, we will replace any digit of this new array with the last digit fixed in the array and again make permutations of this array. For example, After making all the permutations of the numbers 3 and 4, i.e {3 4} and {4 3} and getting the numbers {1 2 3 4} and {1 2 4 3}, we replaced {2} with {3} (2 was the lastly fixed digit of the number ). Now, the last two digits of the number are {2} and {4}. Now, we made the permutation of these digits and will get {1 3 2 4} and {1 3 4 2}.

Similarly, after getting all the permutations of the last three digits of an array, we will replace the first index and get all the permutations of the last three indexes.

So logic should be clear by now, so let’s Code the above solution.

Implementation in Java

import java.util.*;

public class A {
   static void permutations(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> nums, int l, int h) {
       if (l == h) {
           ArrayList<Integer> nums1 = new ArrayList<Integer>(nums);

           res.add(nums1);
           return;
       }
       for (int i = l; i <= h; i++) {

           // Swapping
           int left = nums.get(l);
           nums.set(l, nums.get(i));
           nums.set(i, left);

           // Calling permutations for
           // next greater value of l
           permutations(res, nums, l + 1, h);

           // Backtracking
           left = nums.get(l);
           nums.set(l, nums.get(i));
           nums.set(i, left);
       }
   }

   static ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> nums) {
       // Declaring result variable
       ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer> >();
       int x = nums.size() - 1;
       // Calling permutations for the first
       // time by passing l
       // as 0 and h = nums.size()-1
       permutations(res, nums, 0, x);
       return res;
   }

   public static void main(String[] args) {
       ArrayList<Integer> nums = new ArrayList<Integer>();
       nums.add(1);
       nums.add(2);
       nums.add(4);
       ArrayList<ArrayList<Integer>> res = permute(nums);

       Set<ArrayList<Integer>> hs = new HashSet<ArrayList<Integer>>();

       for (int i=0;i<res.size();i++){
           hs.add(res.get(i));
       }
       System.out.println("There are " + hs.size() + "possible permutations");
       res.forEach(System.out::println);
      
   }
}

Implementation in Python

# Function to find the all possible permutations
def permutations(res,nums,l,h):
    # Base case
    # Add the vector to result and return
    if l==h:
        res.append(nums[:])
        return


    # Permutations made
    for i in range(l,h+1):
        nums[l],nums[i]=nums[i],nums[l]
        # Calling permutations for
        # next greater value of l
        permutations(res,nums,l+1,h)
        nums[l],nums[i]=nums[i],nums[l]


# Function to get the all possible permutations
def permute(nums):
    res = []
    x = len(nums)-1
    # Calling permutations for the first
    # time by passing l
    # as 0 and h = nums.size()-1
    permutations(res,nums,0,x)
    return res


nums = [1,2,4]
res = permute(nums)
s = set()
for x in res:
    s.add(tuple(x))


print("there are ",len(s),"possible permutations")


for x in s:
    for y in x:
        print(y,end=" ")
    print()

Implementation in C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;

// Function for swapping two numbers
void swap(int& x, int& y)
{
   int temp = x;
   x = y;
   y = temp;
}

// Function to find the all possible permutations
void permutations(vector<vector<int> >& res,
            vector<int> nums, int l, int h)
{
   // Base case
   // Add the vector to result and return
   if (l == h) {
      res.push_back(nums);
      return;
   }

   // Permutations made
   for (int i = l; i <= h; i++) {

      // Swapping
      swap(nums[l], nums[i]);

      // Calling permutations for
      // next greater value of l
      permutations(res, nums, l + 1, h);

      // Backtracking
      swap(nums[l], nums[i]);
   }
}

// Function to get the all possible permutations
vector<vector<int> > permute(vector<int>& nums)
{
   // Declaring result variable
   vector<vector<int> > res;
   int x = nums.size() - 1;

   // Calling permutations for the first
   // time by passing l
   // as 0 and h = nums.size()-1
   permutations(res, nums, 0, x);
   return res;
}

// Driver Code
int main()
{
   vector<int> nums = { 1, 2, 4 };
   vector<vector<int> > res = permute(nums);

   // printing result
   set<vector<int>>s;

   for (auto x : res) {
        s.insert(x);
   }
    cout << "There are " << s.size() << " possible permuatations" << endl;
   for(auto x : s){
        for(auto y : x)
            cout << y << " ";
        cout << endl;
   }

   return 0;
}

 

Output:

 There are 6 possible permutations
1 2 4
1 4 2
2 1 4
2 4 1
4 1 2
4 2 1

Complexity Analysis

Time Complexity: O(N*N!)

Explanation: N is the time for printing all possible permutations and there are total N! Possible permutations. 

Space ComplexityO(N)

Frequently asked questions

What is the difference between backtracking and recursion?

In recursion, we use the function calls themselves until it reaches a base case, while in case of backtracking, we use recursion to explore all the possibilities until we get the best result for the problem.

How many permutations if there are some identical elements? 

Repetitions in the array are taken care of by dividing the permutation by the factorial of the number of identical objects. 

What is the sum of all possible combinations of a given array of size n? 

The sum of all possible combinations of n distinct things is 2 n. 

C0 + nC1 + nC2 + . . . nC n = 2 n.

Conclusion

This article discussed the problem of printing all possible permutations of an array without duplicates. We hope you understand the problem and solution properly. Now you can try the more similar questions on Binary Search Tree

Some problems are suggested for you on the permutations topic-

Permutations

Find Permutation

Number of squareful arrays

Check Permutation

 

If you are a beginner, interested in coding, and want to learn Data Structure and Algorithms, check out our courses, Top Array Coding Interview Questions and problems, available on CodeStudio, which is free! 

Moreover, you can visit different sets of problems on Backtracking and Recursion available on CodeStudio, to ace the interviews of reputed product-based companies like Amazon, Microsoft, Google, and more. Attempt our mock test series and participate in the contests hosted on CodeStudio now! Also, look at the interview experiences and interview bundle for placement preparations.

On the other hand, learning never ceases, and there is always more to learn. So, keep learning and keep growing, ninjas!

Good luck with your preparation!


Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think