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

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

Answer 2

The map and reduce approach

• The input list, may contain duplicates.

  List<String> list = Arrays.asList("", "", "");
  

• The map method represents each element of a list as a list of permutation maps.

  1: [{0=}, {1=}, {2=}]
  2: [{0=}, {1=}, {2=}]
  3: [{0=}, {1=}, {2=}]
  

• The reduce method sequentially sums pairs of these lists and concatenates pairs of maps into a single list of maps of permutations.

  {0=, 1=, 2=}
  {0=, 2=, 1=}
  {1=, 0=, 2=}
  {1=, 2=, 0=}
  {2=, 0=, 1=}
  {2=, 1=, 0=}
  

Try it online!

public static void main(String[] args) {
    // input list
    List<String> list = Arrays.asList("", "", "");
    // possible permutations
    List<Map<Integer, String>> pp = possiblePermutations(list);
    // output
    pp.forEach(System.out::println);
}

/**
 * @param list the input list, may contain duplicates
 * @param <E>  the type of the element of the list
 * @return the list of possible permutations
 */
public static <E> List<Map<Integer, E>> possiblePermutations(List<E> list) {
    // check if the list is non-null and non-empty
    if (list == null || list.size() == 0) return Collections.emptyList();
    return IntStream.range(0, list.size())
            // represent each list element as a list of permutation maps
            .mapToObj(i -> IntStream.range(0, list.size())
                    // key - element position, value - element itself
                    .mapToObj(j -> Collections.singletonMap(j, list.get(j)))
                    // Stream<List<Map<Integer,E>>>
                    .collect(Collectors.toList()))
            // reduce a stream of lists to a single list
            .reduce((list1, list2) -> list1.stream()
                    .flatMap(map1 -> list2.stream()
                            // filter out those keys that are already present
                            .filter(map2 -> map2.keySet().stream()
                                    .noneMatch(map1::containsKey))
                            // concatenate entries of two maps, order matters
                            .map(map2 -> new LinkedHashMap<Integer, E>() {{
                                putAll(map1);
                                putAll(map2);
                            }}))
                    // list of combinations
                    .collect(Collectors.toList()))
            // otherwise an empty collection
            .orElse(Collections.emptyList());
}

---

^{See also: String permutations using recursion in Java}

Answer 3

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

Answer 4

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

Answer 5

You can keep the start fixed and then keep swapping. It is one of the easiest approaches to understand.

public class PermutationListRecursion {
    private Set<List<Integer>> permList = new HashSet<>();

    public static void main(String[] args) {
        PermutationListRecursion pt = new PermutationListRecursion();
        Integer[] nums = {1, 2, 3};
        pt.permute(nums);
        System.out.println(pt.permList);
    }

    public void permute(Integer[] nums) {
        permutation(0, nums.length - 1, nums);
    }

    public void permutation(int start, int end, Integer[] nums) {
        if (start == end) {
            permList.add(new ArrayList<Integer>(Arrays.asList(nums)));
        }
        for (int i = start; i <= end; i++) {
            permList.add(swap(nums, start, i));
            permutation(start + 1, end, nums);
            permList.add(swap(nums, start, i));
        }
    }

    private List<Integer> swap(Integer[] arr, int a, int b) {
        if (a == b) {
            return new ArrayList<>(Arrays.asList(arr));
        }
        Integer temp = arr[b];
        arr[b] = arr[a];
        arr[a] = temp;
        return new ArrayList<>(Arrays.asList(arr));
    }
}

Answer 6

I looked into this thread and I analyzed the solutions which are correct. Unfortunately, i need this recursion for a huge input which will result in creating a lot of objects which I don't need stored, I want to apply a method on every permutation and keep only those which satisfy my algorithm so I came up with this solution. Hope it will help others.

public static <E> void iteratePermutations(List<E> original, Consumer<List<E>> consumer) {
    Objects.requireNonNull(original);
    consumer.accept(original);
    iteratePermutationsRecursively(original, 0, consumer);
}

public static <E> void iteratePermutationsRecursively(List<E> original, int start, Consumer<List<E>> consumer) {
    Objects.requireNonNull(original);
    for (int i = start; i < original.size() - 1; i++) {
        for (int j = i + 1; j < original.size(); j++) {
            List<E> temp = new ArrayList<>(original);
            E tempVal = temp.get(i);
            temp.set(i, temp.get(j));
            temp.set(j, tempVal);
            consumer.accept(temp);
            iteratePermutationsRecursively(temp, i + 1, consumer);
        }
    }
}

I can be called as:

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
List<List<Integer>> result = new ArrayList<>();
iteratePermutations(list, result::add);

or:

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
iteratePermutations(list, System.out::println);

Answer 7

Here is my solution to this permutation challenge, I use the DFS Algorithm to build a permutations tree, which I prune depending on the size of the required subset.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

    /**
    * Permuation Application
    * This class works out all permutations of a given set of elements
    * 
    * @author arshadmayet
    *
    */
    public class Permutation {
    
    public static final String EMPTY_STRING = "";
    
    /**
     * DFS Algorithm to find all permutaions on a sequence of elements
     * 
     * @param pref        path of current element in permutation tree
     * @param result      to store permutations
     * @param sequence    list of elements to permutate
     * @param subset      subset size, use size of sequence for the 
     *                    entire size per permutation.
     * @return all permutations of the given sequence as a String List                    
     */
     public List<String> permutate(String pref, List<String> result, 
            List<String> sequence, int subset) {
            
        /*
         * Get just the unvisited children for tree element
         */
        List<String> diff = sequence.stream().filter(x -> ! 
                     (pref).contains(x)).collect(Collectors.toList());

        /*
         * No more children therefore reached end of branch store branch paths
         */
         int limit = sequence.size() - subset;
         if(diff.size()==limit){
            result.add(pref);
         }

        /*
         * Loop thru each child
         */
         for (String s : diff) {
            if(pref.length()>subset) break; // to trim permuatation tree based on 
                                          // result sequence limit
            permutate(pref + s, result,sequence,subset); // recursively traverse 
                                                       //tree
        }
        return result;
    }

    public static void main(String[] args) {
    
        Permutation permutation = new Permutation();
        
        // Test 1
        String[] sequenceArray1 = { "1", "2", "3" };
        List<String> sequence1 = Arrays.asList(sequenceArray1);
        int subset1= sequence1.size();  //subset
        List<String> results1 =  permutation.permutate(EMPTY_STRING,
                                        new ArrayList<String>(),
                                        sequence1,
                                        subset1);
        
        //Display Logic
        System.out.println("Test 1");
        System.out.println("Sequence "+sequence1);
        System.out.println("Subset "+subset1);
        System.out.println(results1);
        System.out.println("results size = " + results1.size());

        System.out.println();

        //Test 2
        String[] sequenceArray2 = {"1","2","3","4"};
        List<String> sequence2 = Arrays.asList(sequenceArray2);
        int subset2= 2;  //subset
        List<String> results2 =  permutation.permutate(EMPTY_STRING,
                                        new ArrayList<String>(),
                                        sequence2,
                                        subset2);
        
        //Display Logic
        System.out.println("Test 2");
        System.out.println("Sequence "+sequence2);
        System.out.println("Subset "+subset2);
        System.out.println(results2);
        System.out.println("results size = " + results2.size());
    }
}

Output:

Test 1
Sequence [1, 2, 3]
Subset 3
[123]
[132]
[213]
[231]
[312]
[321]
results size = 6

Test 2
Sequence [1, 2, 3, 4]
Subset 2
[12]
[13]
[14]
[21]
[23]
[24]
[31]
[32]
[34]
[41]
[42]
[43]
results size = 12