在Java中实现置换算法的技巧

Question

作为学校项目的一部分,我需要编写一个函数,该函数将采用整数N并返回数组{0,1,...,N-1}的每个排列的二维数组.声明看起来像public static int [] [] permutations(int N).

http://www.usna.edu/Users/math/wdj/book/node156.html中描述的算法是我决定实现它的方法.

我使用ArrayLists的数组和数组以及ArrayLists的ArrayLists进行了一段时间的摔跤,但到目前为止,我一直很沮丧,特别是试图将2d ArrayList转换为2d数组.

所以我用javascript编写了它.这有效:

function allPermutations(N) {
    // base case
    if (N == 2) return [[0,1], [1,0]];
    else {
        // start with all permutations of previous degree
        var permutations = allPermutations(N-1);

        // copy each permutation N times
        for (var i = permutations.length*N-1; i >= 0; i--) {
            if (i % N == 0) continue;
            permutations.splice(Math.floor(i/N), 0, permutations[Math.floor(i/N)].slice(0));
        }

        // "weave" next number in
        for (var i = 0, j = N-1, d = -1; i < permutations.length; i++) {
            // insert number N-1 at index j
            permutations[i].splice(j, 0, N-1);

            // index j is  N-1, N-2, N-3, ... , 1, 0; then 0, 1, 2, ... N-1; then N-1, N-2, etc.
            j += d;
            // at beginning or end of the row, switch weave direction
            if (j < 0 || j >= N) {
                d *= -1;
                j += d;
            }
        }
        return permutations;
    }
}

那么将它移植到Java的最佳策略是什么？我可以用原始数组做到吗？我需要一个ArrayLists数组吗？还是ArrayLists的ArrayList？或者是否有其他数据类型更好？无论我使用什么,我都需要能够将它转换回一个原始数组的数组.

也许有一个更好的算法可以简化这个...

提前感谢您的建议!

Answer 1

如你所知,预先排列的排列数(它是N!),你也想要/必须返回一个int[][]我会直接找到一个数组.您可以在开头用正确的尺寸声明它并在最后返回它.因此,您根本不必担心之后转换它.

Answer 2

根据霍华德的建议，我决定除了原始数组类型之外不想使用任何东西。我最初选择的算法在 Java 中实现起来很痛苦，因此感谢 stalker 的建议，我选择了Wikipedia 中描述的字典顺序算法。这就是我最终得到的结果：

public static int[][] generatePermutations(int N) {
    int[][] a = new int[factorial(N)][N];
    for (int i = 0; i < N; i++) a[0][i] = i;
    for (int i = 1; i < a.length; i++) {
        a[i] = Arrays.copyOf(a[i-1], N);
        int k, l;
        for (k = N - 2; a[i][k] >= a[i][k+1]; k--);
        for (l = N - 1; a[i][k] >= a[i][l]; l--);
        swap(a[i], k, l);
        for (int j = 1; k+j < N-j; j++) swap(a[i], k+j, N-j);
    }
    return a;
}
private static void swap(int[] is, int k, int l) {
    int tmp_k = is[k];
    int tmp_l = is[l];
    is[k] = tmp_l;
    is[l] = tmp_k;
}