Given a collection of numbers, return all possible permutations.
Problem description:
Input:list of numbers: [8, 4, 13]
Output:
all permutations of the numbers in the list
[8, 4, 13]
[4, 8, 13]
[4, 13, 8]
[8, 13, 4]
[13, 8, 4]
[13, 4, 8]
Solution 1:
/**
* do it iteratively
*/
* do it iteratively
*/
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
//start with an empty list
result.add(new ArrayList<Integer>());
for(int i=0; i<nums.length; i++){
ArrayList<ArrayList<Integer>> temp = new ArrayList<>();
//go through the list from previous round and add the number into the list
for(ArrayList<Integer> each : result){
for(int index = 0; index<=each.size(); index++){
ArrayList<Integer> dest = new ArrayList<>(each); //make a copy of original list
dest.add(index, nums[i]); //insert the number into all possible positions
temp.add(dest);
}
}
// switch over to prepare for the next round
result = temp;
}
return result;
}
Solution 2:
/**
* do it recursively
**/
public static List<List<Integer>> getPermutations(List<Integer> nums){
List<List<Integer>> result = new ArrayList<>();
if(nums.size()==0){
result.add(new ArrayList<Integer>());
return result;
}
Integer n = nums.remove(0);
List<List<Integer>> subResult = getPermutations(nums); //get the permutation for sub list
for(List<Integer> each : subResult){
for(int index = 0; index<=each.size(); index++){
ArrayList<Integer> dest = new ArrayList<>(each); //make a copy of original list
dest.add(index, n); //insert the number into all possible positions
result.add(dest);
}
}
return result;
}
No comments:
Post a Comment