Generating all possible permutations of a list recursively
If allPossibleItems
contains two different elements, x and y, then you successively write x and y to the list until it reaches DESIRED_SIZE
. Is that what you really want? If you pick DESIRED_SIZE
sufficiently large, you will have too many recursive calls on the stack, hence the SO exception.
What I'd do (if original has no douplets / duplicates) is:
public <E> List<List<E>> generatePerm(List<E> original) {
if (original.isEmpty()) {
List<List<E>> result = new ArrayList<>();
result.add(new ArrayList<>());
return result;
}
E firstElement = original.remove(0);
List<List<E>> returnValue = new ArrayList<>();
List<List<E>> permutations = generatePerm(original);
for (List<E> smallerPermutated : permutations) {
for (int index = 0; index <= smallerPermutated.size(); index++) {
List<E> temp = new ArrayList<>(smallerPermutated);
temp.add(index, firstElement);
returnValue.add(temp);
}
}
return returnValue;
}
The problem is that you have to clone the ArrayList before making the recursive call. Otherwise you will be adding always to the same ArrayList.
//allPossibleItems is an AL of all items
//this is called with generatePerm(null, new ArrayList<Item>);
private void generatePerm(Item i, ArrayList<Item> a) {
if (i != null) { a.add(i); }
if (a.size() == DESIRED_SIZE) {
permutations.add(a);
return;
}
for (int j = 0; j < allPossibleItems.size(); j++) {
if (!a.contains(allPossibleItems.get(j))) {
ArrayList<Item> b = clone(a);
generatePerm(allPossibleItems.get(j), b);
}
}
}