Permutation algorithm for array of integers in Java

Question

I have a working example to generate all char permutations in a String as below:

static ArrayList<String> permutations(String s) {
        if (s == null) {
            return null;
        }

        ArrayList<String> resultList = new ArrayList<String>();

        if (s.length() < 2) {
            resultList.add(s);

            return resultList;
        }

        int length = s.length();
        char currentChar;

        for (int i = 0; i < length; i++) {
            currentChar = s.charAt(i);

            String subString = s.substring(0, i) + s.substring(i + 1);

            ArrayList<String> subPermutations = permutations(subString);

            for (String item : subPermutations) {
                resultList.add(currentChar + item);
            }
        }

        return resultList;
    } 

I am trying to implement the same function, but to return ArrayList, and to get int[] as the parameter. I am doing this recursively as below:

static ArrayList<int[]> permutations(int[] arr) {
        ArrayList<int[]> resultList = new ArrayList<int[]>();

        if (arr.length < 2) {
            resultList.add(arr);

            return resultList;
        } 

        for (int i = 0; i < arr.length; i++) {
            int currentItem = arr[i];
            int[] newArr = new int[arr.length - 1];
            int[] newPermutation = new int[arr.length];
            int j;

//          System.arraycopy(arr, 0, newArr, 0, i);
//          System.arraycopy(arr, i + 1, newArr, i, arr.length - i - 1);

            for (j = 0; j < i; j++) {
                newArr[j] = arr[j];
            }

            for (j = i + 1; j < arr.length; j++) {
                newArr[j - 1] = arr[j];
            }

            ArrayList<int[]> subPermutations = permutations(newArr);

            newPermutation[0] = currentItem;

//          for (int i1 = 0; i1 < subPermutations.size(); i1++) {
//              for (j = 0; j < subPermutations.get(i1).length; j++) {
//                  newPermutation[j + 1] = subPermutations.get(i1)[j];
//              }
//              
//              resultList.add(newPermutation);
//          }

            for (int[] item : subPermutations) {
                for (j = 0; j < item.length; j++) {
                    newPermutation[j + 1] = item[j];
                }

                resultList.add(newPermutation);
            }

//          return resultList;
        }

        return resultList;
    }

When passing arrays of size 0, 1, and 2 as the parameter, everything is fine. For everything else greater than 2, I get the correct number of permutations, but they repeat themselves. Here is the result for size == 3, and passing { 1, 5, 4 }:

1 4 5 
1 4 5 
5 4 1 
5 4 1 
4 5 1 
4 5 1

Please give me some advice if you encountered these issues before.

Thanks in advance!

Answer 1

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

Answer 2

import java.util.ArrayList;
import java.util.Arrays;

public class Answer {
    static <E> String arrayToString( E[] arr ) {
        final StringBuffer str = new StringBuffer();
        for ( E e : arr )
            str.append( e.toString() );
        return str.toString();
    }

    static <E> ArrayList<E[]> permutations(E[] arr) {
        final ArrayList<E[]> resultList = new ArrayList<E[]>();
        final int l = arr.length;
        if ( l == 0 ) return resultList;
        if ( l == 1 )
        {
            resultList.add( arr );
            return resultList;
        }

        E[] subClone = Arrays.copyOf( arr, l - 1);
        System.arraycopy( arr, 1, subClone, 0, l - 1 );

        for ( int i = 0; i < l; ++i ){
            E e = arr[i];
            if ( i > 0 ) subClone[i-1] = arr[0];
            final ArrayList<E[]> subPermutations = permutations( subClone );
            for ( E[] sc : subPermutations )
            {
                E[] clone = Arrays.copyOf( arr, l );
                clone[0] = e;
                System.arraycopy( sc, 0, clone, 1, l - 1 );
                resultList.add( clone );
            }
            if ( i > 0 ) subClone[i-1] = e;
        }
        return resultList;
    }

    static ArrayList<String> permutations(String arr) {
        final Character[] c = new Character[ arr.length() ];
        for ( int i = 0; i < arr.length(); ++i )
            c[i] = arr.charAt( i );

        final ArrayList<Character[]> perms = permutations(c);
        final ArrayList<String> resultList = new ArrayList<String>( perms.size() );

        for ( Character[] p : perms )
        {
            resultList.add( arrayToString( p ) );
        }
        return resultList;
    }

    public static void main(String[] args) {
        ArrayList<String> str_perms = permutations( "abc" );
        for ( String p : str_perms ) System.out.println( p );

        ArrayList<Integer[]> int_perms = permutations( new Integer[]{ 1, 2, 3, 4 } );
        for ( Integer[] p : int_perms ) System.out.println( arrayToString( p ) );

    }
}