Permute an array and saving each result to an ArrayList

Question

I need to permute an array and save each permutation in an arrayList, I am using a recursive method but it is repeatedly saving just one result.

private static List<int[]> permutations = new ArrayList<int[]>();
int array[] = new int[]{1,2,3,4};

public static void permuteArray(int[] array) {
    permuteArray(array, 0);

}

private static void permuteArray(int[] array, int index) {
    if (index == array.length - 1) {
        permutations.add(array);
    }

    for (int i = index; i < array.length; i++) {

        int aux = array[index];
        array[index] = array[i];
        array[i] = aux;

        permuteArray(array, index + 1);

        aux = array[index];
        array[index] = array[i];
        array[i] = aux;

    }
}

Answer 1

I found this implementation I have created quite useful especially since it avoids massive creation of objects like collections, it is all based on int[] arrays.

The method at the top does all the recursive heavy-lifting and the three generate() methods at the bottom show example invocations. You can invoke this with an int[] array or with a string which is then split into char[] ... the computation works for integers as well as chars, you just need to cast them back to char for the output afterwards. The first generate() method just creates an int[] of length n and fills it with 0, 1, ..., n-1 for convenience.

To get the permutations, just iterate over the first dimension of the int[][], the second dimension holds the values.

public class Permutations {

    private int[][] permutations;
    private int resultIndex = 0;

    private void permutate(int[] resultCollector, int resultCollectorIndex, int[] permutableValues) {
        if (permutableValues.length > 0) {
            for (int i = 0; i < permutableValues.length; i++) {
                int[] nextResultCollector = Arrays.copyOf(resultCollector, resultCollector.length);
                nextResultCollector[resultCollectorIndex] = permutableValues[i];
                permutate(nextResultCollector, resultCollectorIndex + 1, reduce(permutableValues, i));
            }
        } else {
            System.arraycopy(resultCollector, 0, permutations[resultIndex], 0, resultCollector.length);
            resultIndex++;
        }
    }

    private int[] reduce(int[] d, int k) {
        int[] r = new int[d.length - 1];
        int ind = 0;
        for (int i = 0; i < d.length; i++) {
            if (i != k) {
                r[ind++] = d[i];
            }
        }
        return r;
    }

    public int[][] generate(int n) {
        int permutationCount = factorial(n);
        permutations = new int[permutationCount][n];
        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = i;
        }
        return generate(d);
    }

    public int[][] generate(String input) {
        int[] d = new int[input.length()];
        for (int i = 0; i < input.length(); i++) {
            d[i] = input.charAt(i);
        }
        return generate(d);
    }

    public int[][] generate(int[] input) {
        int n = input.length;
        int permutationCount = factorial(n);
        permutations = new int[permutationCount][n];
        permutate(new int[n], 0, input);
        return permutations;
    }
}

Answer 2

You can do it as follows:

public class Permutation {
    public static void main(String[] args) {
        java.util.List<StringBuilder> result=new java.util.ArrayList<StringBuilder>();
        permute(java.util.Arrays.asList(1,2,3,4), 0,result);
        for(StringBuilder sb:result)
            System.out.println(sb.toString());
    }

    static void permute(java.util.List<Integer> arr, int k, java.util.List<StringBuilder> result){
        for(int i = k; i < arr.size(); i++){
            java.util.Collections.swap(arr, i, k);
            permute(arr, k+1,result);
            java.util.Collections.swap(arr, k, i);
        }
        if (k == arr.size() -1){
            result.add(new StringBuilder(java.util.Arrays.toString(arr.toArray())));      
        }
    }
}

Output:

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 3, 2]
[1, 4, 2, 3]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[2, 4, 1, 3]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 2, 3, 1]
[4, 2, 1, 3]
[4, 3, 2, 1]
[4, 3, 1, 2]
[4, 1, 3, 2]
[4, 1, 2, 3]