Question 32 : Permutations of array in java.

 Given array of distinct integers, print all permutations of the array.

For example :

array : [10, 20, 30]
 
Permuations are :
 
[10, 20, 30]
[10, 30, 20]
[20, 10, 30]
[20, 30, 10]
[30, 10, 20]
[30, 20, 10]

We can solve the problem with the help of recursion. It is quite hard to explain recursion, so I have created a recursion tree to demonstrate it.

Here is the code for the same.

import java.util.ArrayList;
import java.util.List;
 
public class PermutateArray {
 
    public static void main(String[] args) {
        PermutateArray pa=new PermutateArray();
 
        int[] arr= {10, 20, 30};
 
        List<List<Integer>> permute = pa.permute(arr);
 
        System.out.println("Permuations of array : [10, 20, 30] are:");
        System.out.println("=========================================");
        for(List<Integer> perm:permute)
        {
            System.out.println(perm);
        }
 
    }
    public List<List<Integer>> permute(int[] arr) {
        List<List<Integer>> list = new ArrayList<>();
        permuteHelper(list, new ArrayList<>(), arr);
        return list;
    }
 
    private void permuteHelper(List<List<Integer>> list, List<Integer> resultList, int [] arr){
 
        // Base case
        if(resultList.size() == arr.length){
            list.add(new ArrayList<>(resultList));
        } 
        else{
            for(int i = 0; i < arr.length; i++){ 
 
                if(resultList.contains(arr[i])) 
                {
                    // If element already exists in the list then skip
                    continue; 
                }
                // Choose element
                resultList.add(arr[i]);
                // Explore
                permuteHelper(list, resultList, arr);
                // Unchoose element
                resultList.remove(resultList.size() - 1);
            }
        }
    } 

When you run above program, you will get below output:

Permuations of array : [10, 20, 30] are:
=========================================
[10, 20, 30] [10, 30, 20] [20, 10, 30] [20, 30, 10] [30, 10, 20] [30, 20, 10]

have illustrated how recursion is working here with below diagram.

Problem 2

Given array of integers(can contain duplicates), print all permutations of the array.

---

Solution

We can solve this using recursion as well but need to take care of duplicates.We will sort the array, so all duplicates will be conitguous.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class PermuteArrayWithDuplicates {
 
    public static void main(String[] args) {
        PermuteArrayWithDuplicates pa=new PermuteArrayWithDuplicates();
 
        int[] arr= {10, 20, 10};
 
        List<List<Integer>> permute = pa.permute(arr);
 
        System.out.println("Permuations of array : [10, 20, 10] are:");
        System.out.println("=========================================");
        for(List<Integer> perm:permute)
        {
            System.out.println(perm);
        }
 
    }
    public List<List<Integer>> permute(int[] arr) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(arr);
        permuteHelper(list, new ArrayList<>(), arr,new boolean[arr.length]);
        return list;
    }
 
    private void permuteHelper(List<List<Integer>> list, List<Integer> resultList, int [] arr, boolean [] used){
 
        // Base case
        if(resultList.size() == arr.length){
            list.add(new ArrayList<>(resultList));
        } else{
            for(int i = 0; i < arr.length; i++){
                if(used[i] || i > 0 && arr[i] == arr[i-1] && !used[i - 1]) 
                {   
                        // If element is already used
                        continue;
                }
                // choose element
                used[i] = true; 
                resultList.add(arr[i]);
 
                // Explore
                permuteHelper(list, resultList, arr, used);
 
                // Unchoose element
                used[i] = false; 
                resultList.remove(resultList.size() - 1);
            }
        }
    }
 
}

Permuations of array : [10, 20, 10] are:
=========================================
[10, 10, 20] [10, 20, 10] [20, 10, 10]

Don't miss the next article! 
Be the first to be notified when a new article or Kubernetes experiment is published.                            

   

Share This

• Facebook

• Twitter

• Linkedin

• Pinterest