Permutation algorithm for array of integers in Java

by

//Here is a recursive version that was not to hard to commit to human memory ! O(n!) permutations.

public static Set<Integer[]> getPermutationsRecursive(Integer[] num){
    if (num == null)
        return null;

    Set<Integer[]> perms = new HashSet<>();

    //base case
    if (num.length == 0){
        perms.add(new Integer[0]);
        return perms;
    }

    //shave off first int then get sub perms on remaining ints.
    //...then insert the first into each position of each sub perm..recurse

    int first = num[0];
    Integer[] remainder = Arrays.copyOfRange(num,1,num.length);
    Set<Integer[]> subPerms = getPermutationsRecursive(remainder);
    for (Integer[] subPerm: subPerms){
        for (int i=0; i <= subPerm.length; ++i){ // '<='   IMPORTANT !!!
            Integer[] newPerm = Arrays.copyOf(subPerm, subPerm.length+1);
            for (int j=newPerm.length-1; j>i; --j)
                newPerm[j] = newPerm[j-1];
            newPerm[i]=first;
            perms.add(newPerm);
        }
    }

    return perms;
}

More Related Contents:

  1. How to check two array list are same content in same position
  2. Write a program that takes an array/arraylist of integer and finds longest sub array/arraylist whose entries are equal [closed]
  3. Android String that change every day
  4. Create ArrayList from array
  5. How can I avoid ArrayIndexOutOfBoundsException or IndexOutOfBoundsException? [duplicate]
  6. Converting ‘ArrayList to ‘String[]’ in Java
  7. Convert ArrayList to String[] array [duplicate]
  8. Convert list to array in Java [duplicate]
  9. How to convert an ArrayList containing Integers to primitive int array?
  10. What is the diamond operator in Java? [duplicate]
  11. How can I create an Array of ArrayLists?
  12. Java: Detect duplicates in ArrayList?
  13. Variable length (Dynamic) Arrays in Java
  14. make arrayList.toArray() return more specific types
  15. Distinction between the capacity of an array list and the size of an array
  16. How do I declare a 2D String arraylist?
  17. Print ArrayList
  18. Using contains on an ArrayList with integer arrays
  19. Arrays.asList() of an array
  20. ArrayList: how does the size increase?
  21. casting Arrays.asList causing exception: java.util.Arrays$ArrayList cannot be cast to java.util.ArrayList
  22. Time Complexity for Java ArrayList
  23. How can I create an array in Kotlin like in Java by just providing a size?
  24. Converting an ArrayList into a 2D Array
  25. Java ArrayList how to add elements at the beginning
  26. Create an array of ArrayList elements
  27. Assigning an array to an ArrayList in Java
  28. Comparing arrays in JUnit assertions, concise built-in way?
  29. Fastest way to set all values of an array?
  30. Add ArrayList to another ArrayList in java

Leave a Comment