Generating all possible permutations of a list recursively

by

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

More Related Contents:

  1. How to generate a random permutation in Java?
  2. Modulus of a very large number
  3. Fast algorithm to calculate n! / (q!)^r
  4. O(3^n) exponential time complexity [closed]
  5. Showing the order of growth of the function
  6. Good Java graph algorithm library? [closed]
  7. Sparse matrices / arrays in Java
  8. Which Java Collection should I use?
  9. Natural sort order string comparison in Java – is one built in? [duplicate]
  10. Quickest way to find missing number in an array of numbers
  11. How to calculate elapsed time from now with Joda-Time?
  12. Java, find intersection of two arrays
  13. Calculating all of the subsets of a set of numbers
  14. Stack with find-min/find-max more efficient than O(n)?
  15. How to convert a byte array to its numeric value (Java)?
  16. Java – Removing duplicates in an ArrayList
  17. Why does Java’s Arrays.sort method use two different sorting algorithms for different types?
  18. Parallel execution of directed acyclic graph of tasks
  19. Find top N elements in an Array
  20. Java – Sort one array based on values of another array?
  21. What is the sorting algorithm for Java [closed]
  22. In Java, how do I efficiently and elegantly stream a tree node’s descendants?
  23. Flatten nested arrays in java
  24. How to generate the power-set of a given List?
  25. Permutation algorithm for array of integers in Java
  26. How to restore the PriorityQueue to its initial state before the method call?
  27. How to determine if binary tree is balanced?
  28. Determine the most common occurrence in an array
  29. Hash : How does it work internally?
  30. What is the algorithm for finding the center of a circle from three points?

Leave a Comment