Перестановка массива и сохранение каждого результата в ArrayList

Question

Мне нужно переставить массив и сохранить каждую перестановку в arrayList, я использую рекурсивный метод, но он многократно сохраняет только один результат.

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

Вы можете сделать это следующим образом:

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

Вывод:

[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]

Answer 2

Я нашел эту реализацию, которую я создал, весьма полезной, тем более что она позволяет избежать массового создания таких объектов, как коллекции, и все это основано на массивах int [].

Метод в верхней части выполняет все рекурсивные тяжелые операции, а три метода generate () в нижней части показывают примеры вызовов. Вы можете вызвать это с помощью массива int [] или строки, которая затем разделяется на char [] ... вычисление работает как для целых чисел, так и для символов, вам просто нужно привести их обратно к char для вывода потом. Первый метод generate () просто создает int [] длины n и заполняет его 0, 1, ..., n-1 для удобства.

Чтобы получить перестановки, просто выполните итерацию по первому измерению int [] [], второе измерение содержит значения.

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