java - 在 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 吗？还是 ArrayList 的 ArrayList？还是有其他更好的数据类型？无论我使用什么，我都需要能够将其转换回原始数组的数组。

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

预先感谢您的建议!

Answer 1

正如您事先知道的排列数(它是 N!)并且您希望/必须返回一个 int[][] 我会直接选择一个数组。您可以在开始时使用正确的尺寸声明它并在最后返回它。因此，您完全不必担心事后进行转换。