Wednesday, May 4, 2022

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


You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS