Generating all possible permutations of a list recursively

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}

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

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

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

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

Apache Commons Collections actually provides a PermutationIterator (since 4.0) which can be used to solve this:

public static void main(String[] args) { // Input list List<String> list = Arrays.asList("𝟭", "𝟮", "𝟯"); // Use the PermutationIterator PermutationIterator<String> permutations = new PermutationIterator<>(list); while (permutations.hasNext()) { System.out.println(permutations.next()); } } 

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