Generating all possible permutations of a list recursively

Question

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

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

Solution 3

Googling lead me to this question. i found the below method faster than other methods.

Basically I use a Set to recursively generate the permutations. To illustrate, the first position can hold all possible values, the second all possible values except the first value, and so on. When we get to the last position, there is only one possibility.

In terms of parameters to the recursive function, (1) we pass down what has already been recorded as currentstring. (2) We pass the Arraylist which holds the results - list_of_permutes (3) We pass set from which to choose the current number - currentnums. At the last level, we have a complete permutation, which is then added to the arraylist - list_of_permutes and this is returned upwards.

public static ArrayList recurse_nums(Set<Integer> currentnums,
                                     String currentstring,
                                     ArrayList list_of_permutes) {
    if (currentnums.size() == 1) {
        int elem = currentnums.iterator().next();
        list_of_permutes.add(currentstring + Integer.toString(elem));
        return list_of_permutes;
    }
    for (int a : currentnums) {
        String newstring = currentstring + a;
        Set<Integer> newnums = new HashSet<>();
        newnums.addAll(currentnums);
        newnums.remove(a);
        recurse_nums(newnums, newstring, list_of_permutes);
    }
    return list_of_permutes;
}

This can be called from something like the following:

public static ArrayList permute_array(int[] arr) {
    Set<Integer> currentnums = new HashSet<>();
    for (int i = 0; i < arr.length; i++) {
        currentnums.add(arr[i]);
    }
    ArrayList permutations = new ArrayList();
    recurse_nums(currentnums, "", permutations);
    return permutations;
}

Comments

[moritz]

How would I change the code if I want not all permutations of the same length but I have a given parameter n which reflects the desired size the individual sublists should contain? For example I give the list [1,2,3,4] with n of 2 the I want [[1,2],[1,3], ...] and so forth ?