Write a recursive method public static ArrayList permuteArra

Write a recursive method public static ArrayList permuteArray(int[] array) that returns an ArrayList of all permutations of the the parameter array. The ArrayList may contain the arrays in any order.

Suppose array = {4, 7, 1, 2}. Then the ArrayList would contain the following arrays, but in any order:

4 7 1 2

7 4 1 2

2 1 4 7

1 2 4 7

4 7 2 1

7 4 2 1

2 1 7 4

1 2 7 4

4 2 1 7

7 1 2 4

2 7 4 1

1 4 2 7

4 2 7 1

7 1 4 2

2 7 1 4

1 4 7 2

4 1 2 7

7 2 1 4

2 4 1 7

1 7 2 4

4 1 7 2

7 2 4 1

2 4 7 1

1 7 4 2

Note: You are permitted to use at most two loops in solving this problem. A set of doubly-nested for-loops would count as two loops for this purpose. Recursion must be used in some non-trivial way to help solve the problem. You may write helper methods if you like.

Written in Java

Solution

Java Code:

mport java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Permutations<T> {
public static void main(String args[]) {
Permutations<Integer> obj = new Permutations<Integer>();
Collection<Integer> input = new ArrayList<Integer>();
input.add(4);
input.add(7);
input.add(1);
input.add(2);

Collection<List<Integer>> output = obj.permute(input);
System.out.println(\"Permutations:\"+output);
  
  
}
public Collection<List<T>> permute(Collection<T> input) {
Collection<List<T>> output = new ArrayList<List<T>>();
if (input.isEmpty()) {
output.add(new ArrayList<T>());
return output;
}
List<T> list = new ArrayList<T>(input);
T head = list.get(0);
List<T> rest = list.subList(1, list.size());
for (List<T> permutations : permute(rest)) {
List<List<T>> subLists = new ArrayList<List<T>>();
for (int i = 0; i <= permutations.size(); i++) {
List<T> subList = new ArrayList<T>();
subList.addAll(permutations);
subList.add(i, head);
subLists.add(subList);
}
output.addAll(subLists);
}
return output;
}
}

Output:

run:
Permutations:[[4, 7, 1, 2], [7, 4, 1, 2], [7, 1, 4, 2], [7, 1, 2, 4], [4, 1, 7, 2], [1, 4, 7, 2], [1, 7, 4, 2], [1, 7, 2, 4], [4, 1, 2, 7], [1, 4, 2, 7], [1, 2, 4, 7], [1, 2, 7, 4], [4, 7, 2, 1], [7, 4, 2, 1], [7, 2, 4, 1], [7, 2, 1, 4], [4, 2, 7, 1], [2, 4, 7, 1], [2, 7, 4, 1], [2, 7, 1, 4], [4, 2, 1, 7], [2, 4, 1, 7], [2, 1, 4, 7], [2, 1, 7, 4]]
BUILD SUCCESSFUL (total time: 0 seconds)