Generating all possible permutations of a list recursively
algorithm, java, permutation
Solution
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;
}
Problem
I'm trying to recursively generate all items in a list recursively. I've seen a few solutions to similar questions to this, but I haven't been able to get my code to work. Could someone point out how I can fix my code? This is open to all S/O'ers, not just Java people. (Also I should note that it crashes with a SO exception). Sample input: ``` [1, 2, 3] ``` Output: ``` [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] ``` ``` //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 (allPossibleItems.get(j) != i) generatePerm(allPossibleItems.get(j), a); } } ```