Generating all possible permutations of a list recursively

Solution 1:

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;
}

Solution 2:

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);
        }
    }
}