Generating all possible permutations of a list recursively

Question

I am trying to recursively generate all the items in a list recursively. I saw several solutions for similar issues, but I was not able to get my code to work. Can someone please indicate how I can fix my code?

It is open to all S / O'ers, not just Java people.

(I should also note that it crashes with SO exception).

Input Example: [1, 2, 3]

Conclusion: [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 sequentially write x and y to the list until it reaches DESIRED_SIZE . Is that what you really want? If you DESIRED_SIZE are big enough, you will have too many recursive calls on the stack, hence the SO exception.

What would I do (if there are no duplicates in the original):

  public <E> List<List<E>> generatePerm(List<E> original) { if (original.size() == 0) { List<List<E>> result = new ArrayList<List<E>>(); result.add(new ArrayList<E>()); return result; } E firstElement = original.remove(0); List<List<E>> returnValue = new ArrayList<List<E>>(); List<List<E>> permutations = generatePerm(original); for (List<E> smallerPermutated : permutations) { for (int index=0; index <= smallerPermutated.size(); index++) { List<E> temp = new ArrayList<E>(smallerPermutated); temp.add(index, firstElement); returnValue.add(temp); } } return returnValue; } 

Answer 2

The problem is that before making a recursive call, you have to clone ArrayList. Otherwise, you will always add an ArrayList to one.

 //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 3

 private List generatePerm(List a, int depth) { // this is the method definition you want // to generate all permutations, you need cycle thru all elements in your list and for each element // add that element to each member of generatePerm(a, depth - 1); // if you want combinations, you need to remove the element and then call /// generateCombinations with the remaining list } 

Answer 4

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

I mainly use Set for recursively generating permutations. To illustrate: the first position can contain all possible values, the second - all possible values, except the first, and so on. When we get to the last position, there is only one possibility.

From the point of view of the parameters of the recursive function, (1) we transfer what has already been written as a current string. (2) We pass an Arraylist that contains the results - list_of_permutes (3) We pass a set from which you can select the current number - currentnums. At the last level, we have a complete permutation, which is then added to the list array - list_of_permutes and returns up.

 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 may be caused by 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; }