提示实现置换算法在Java中 [英] Tips implementing permutation algorithm in Java

问题描述

免责声明：我是一个可怜的没有经验的本科生，这是我的家庭作业的一部分。我不希望任何人来为我做的，但方向一点点就会很长的路要走。你的建议将改变我的生活。

Disclaimer: I'm a poor inexperienced undergraduate student, and this is part of my homework. I don't expect anybody to do it for me, but a tiny bit of direction will go a long way. Your advice will change my life.

由于我的项目的一部分，我需要编写一个函数，将采取一个整数N和返回一个二维数组中的每一个置换数组{0，1，...，N-1}。声明看起来像公共静态INT [] []排列（INT N）。

As part of my project, I need to write a function that will take an integer N and return a two-dimensional array of every permutation of the array {0, 1, ..., N-1}. The declaration would look like public static int[][] permutations(int N).

在 http://www.usna.edu/描述的算法用户/数学/ WDJ /电子书/ node156.html 是如何，我已经决定要实现这一点。

The algorithm described at http://www.usna.edu/Users/math/wdj/book/node156.html is how I've decided to implement this.

我搏斗了数组和的ArrayList的阵列和的ArrayList中的ArrayList相当长一段时间，但到目前为止，我已经心灰意冷，尤其是试图将2D的ArrayList转换为二维数组。

I wrestled for quite a while with arrays and arrays of ArrayLists and ArrayLists of ArrayLists, but so far I've been frustrated, especially trying to convert a 2d ArrayList to a 2d array.

所以我在JavaScript写的。这工作：

So I wrote it in javascript. This works:

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？我能做到这一点，只需基本数组？我需要的ArrayList的数组？或者的ArrayLists的ArrayList？或者是有一些其他的数据类型，这是更好吗？不管我用，我需要能够将其转换回原始的数组的数组。

So what's the best strategy to port that to Java? Can I do it with just primitive arrays? Do I need an array of ArrayLists? Or an ArrayList of ArrayLists? Or is there some other data type that's better? Whatever I use, I need to be able to convert it back into a an array of primitive arrays.

也许是有没有更好的算法，将简化这对我来说...

Maybe's there a better algorithm that would simplify this for me...

感谢您提前为您的咨询！

Thank you in advance for your advice!

推荐答案

根据霍华德的建议下，我决定，我不想用任何东西，但基本数组类型。该算法最初我挑是一个痛苦在Java中实现，因此非常感谢死缠烂打的意见，我去的字典下令在Wikipedia 的描述算法。这里是我结束了：

As per Howard's advice, I decided I didn't want to use anything but the primitive array type. The algorithm I initially picked was a pain to implement in Java, so thanks to stalker's advice, I went with the lexicographic-ordered algorithm described at Wikipedia. Here's what I ended up with:

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

这篇关于提示实现置换算法在Java中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！