java - 排列数组并将每个结果保存到 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]