Write a recursive method public static ArrayList permuteArray(int[] array) that
ID: 3777623 • Letter: W
Question
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.
Explanation / Answer
import java.util.ArrayList;
import java.util.Arrays;
public class PermutationArray {
public static ArrayList permuteArray(int[] array) {
ArrayList<String> list = new ArrayList<>();
ArrayList<String> result = new ArrayList<>();
if(array.length == 1) {
list.add(String.valueOf(array[0]));
} else {
int[] tempArray= new int[array.length-1];
int firstElement = array[0];
System.arraycopy(array, 1, tempArray, 0, array.length-1);
list = permuteArray(tempArray);
for (String str:list) {
for(int i=0; i<=str.length(); i++) {
String tempStr = str.substring(0, i)+firstElement+str.substring(i,str.length());
result.add(tempStr);
//System.out.println("str is "+tempStr);
}
}
return result;
}
return list;
}
public static void main(String[] args) {
int[] arr={1,2,3,4,5};
ArrayList aList = permuteArray(arr);
System.out.println(Arrays.toString(aList.toArray()));
System.out.println("Number of elements are "+aList.size());
System.out.println("From Main");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.