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

Tips implementing permutation algorithm in Java

提问by Trevor Dixon

As part of a school 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).

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

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

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

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.

我与ArrayLists的数组和ArrayLists的数组和ArrayLists的ArrayLists搏斗了很长一段时间，但到目前为止我一直很沮丧，尤其是试图将2d ArrayList转换为2d数组。

So I wrote it in javascript. This works:

所以我用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;
    }
}

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.

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

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

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

Thank you in advance for your advice!

预先感谢您的建议！

采纳答案by Trevor Dixon

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:

根据 Howard 的建议，我决定除了原始数组类型之外我不想使用任何东西。我最初选择的算法很难用 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;
}

回答by Howard

As you know the number of permutations beforehand (it's N!) and also you want/have to return an int[][]I would go for an array directly. You can declare it right at the beginning with correct dimensions and return it at the end. Thus you don't have to worry about converting it afterwards at all.

正如您事先知道排列的数量（它是 N！），并且您想要/必须返回一个int[][]I 会直接去寻找一个数组。您可以在开始时使用正确的尺寸声明它并在最后返回它。因此，您根本不必担心事后转换它。

回答by Howard

Since you pretty much had it completed on your own in javascript, I'll go ahead and give you the Java code for implementing Steinhaus' permutation algorithm. I basically just ported your code to Java, leaving as much of it the same as I could, including comments.

由于您几乎已经在 javascript 中自己完成了它，我将继续为您提供用于实现 Steinhaus 置换算法的 Java 代码。我基本上只是将您的代码移植到 Java，尽可能多地保留代码，包括注释。

I tested it up to N = 7. I tried to have it calculate N = 8, but it's been running for almost 10 minutes already on a 2 GHz Intel Core 2 Duo processor, and still going, lol.

我测试了 N = 7。我试图让它计算 N = 8，但它已经在 2 GHz Intel Core 2 Duo 处理器上运行了将近 10 分钟，并且仍在运行，哈哈。

I'm sure if you really worked at it you could speed this up significantly, but even then you're probably only going to be able to squeeze maybe a couple more N-values out of it, unless of course you have access to a supercomputer ;-).

我敢肯定，如果您真的努力工作，您可以显着加快速度，但即使如此，您也可能只能从中挤出更多 N 值，除非您当然可以访问超级计算机;-)。

Warning - this code is correct, NOT robust. If you need it robust, which you usually don't for homework assignments, then that would be an exercise left to you. I would also recommend implementing it using Java Collections, simply because it would be a great way to learn the in's and out's of the Collections API.

警告 - 此代码是正确的，不是健壮的。如果您需要它强大的功能，您通常不会在家庭作业中使用它，那么这将是一个留给您的练习。我还建议使用 Java 集合来实现它，因为这将是了解集合 API 的来龙去脉的好方法。

There's several "helper" methods included, including one to print a 2d array. Enjoy!

包括几种“辅助”方法，包括一种打印二维数组的方法。享受！

Update: N = 8 took 25 minutes, 38 seconds.

更新：N = 8 耗时 25 分 38 秒。

Edit: Fixed N == 1 and N == 2.

编辑：固定 N == 1 和 N == 2。

public class Test
{
  public static void main (String[] args)
  {
    printArray (allPermutations (8));
  }

  public static int[][] allPermutations (int N)
  {
    // base case
    if (N == 2)
    {
      return new int[][] {{1, 2}, {2, 1}};
    }
    else if (N > 2)
    {
      // start with all permutations of previous degree
      int[][] permutations = allPermutations (N - 1);

      for (int i = 0; i < factorial (N); i += N)
      {
        // copy each permutation N - 1 times
        for (int j = 0; j < N - 1; ++j)
        {
          // similar to javascript's array.splice
          permutations = insertRow (permutations, i, permutations [i]);
        }
      }

      // "weave" next number in
      for (int i = 0, j = N - 1, d = -1; i < permutations.length; ++i)
      {
        // insert number N at index j
        // similar to javascript's array.splice
        permutations = insertColumn (permutations, i, j, N);

        // 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 - 1)
        {
          d *= -1;
          j += d;
        }
      }

      return permutations;
    }
    else
    {
      throw new IllegalArgumentException ("N must be >= 2");
    }
  }

  private static void arrayDeepCopy (int[][] src, int srcRow, int[][] dest,
                                     int destRow, int numOfRows)
  {
    for (int row = 0; row < numOfRows; ++row)
    {
      System.arraycopy (src [srcRow + row], 0, dest [destRow + row], 0,
                        src[row].length);
    }
  }

  public static int factorial (int n)
  {
    return n == 1 ? 1 : n * factorial (n - 1);
  }

  private static int[][] insertColumn (int[][] src, int rowIndex,
                                       int columnIndex, int columnValue)
  {
    int[][] dest = new int[src.length][0];

    for (int i = 0; i < dest.length; ++i)
    {
      dest [i] = new int [src[i].length];
    }

    arrayDeepCopy (src, 0, dest, 0, src.length);

    int numOfColumns = src[rowIndex].length;

    int[] rowWithExtraColumn = new int [numOfColumns + 1];

    System.arraycopy (src [rowIndex], 0, rowWithExtraColumn, 0, columnIndex);

    System.arraycopy (src [rowIndex], columnIndex, rowWithExtraColumn,
                      columnIndex + 1, numOfColumns - columnIndex);

    rowWithExtraColumn [columnIndex] = columnValue;

    dest [rowIndex] = rowWithExtraColumn;

    return dest;
  }

  private static int[][] insertRow (int[][] src, int rowIndex,
                                    int[] rowElements)
  {
    int srcRows = src.length;
    int srcCols = rowElements.length;

    int[][] dest = new int [srcRows + 1][srcCols];

    arrayDeepCopy (src, 0, dest, 0, rowIndex);
    arrayDeepCopy (src, rowIndex, dest, rowIndex + 1, src.length - rowIndex);

    System.arraycopy (rowElements, 0, dest [rowIndex], 0, rowElements.length);

    return dest;
  }

  public static void printArray (int[][] array)
  {
    for (int row = 0; row < array.length; ++row)
    {
      for (int col = 0; col < array[row].length; ++col)
      {
        System.out.print (array [row][col] + " ");
      }

      System.out.print ("\n");
    }

    System.out.print ("\n");
  }
}

回答by stalker

The java arrays are not mutable (in the sense, you cannot change their length). For direct translation of this recursive algorithm you probably want to use List interface (and probably LinkedList implementation as you want put numbers in the middle). That is List<List<Integer>>.

java 数组是不可变的（从某种意义上说，你不能改变它们的长度）。对于这种递归算法的直接翻译，您可能想要使用 List 接口（并且可能需要 LinkedList 实现，因为您希望将数字放在中间）。那就是List<List<Integer>>。

Beware the factorial grows rapidly: for N = 13, there is 13! permutations that is 6 227 020 800. But I guess you need to run it for only small values.

当心阶乘快速增长：对于 N = 13，有 13！排列是 6 227 020 800。但我想你只需要为小值运行它。

The algorithm above is quite complex, my solution would be:

上面的算法相当复杂，我的解决方案是：

• create List<int[]>to hold all permutations
• create one array of size N and fill it with identity ({1,2,3,...,N})
• program function that in place creates next permutation in lexicographical ordering
• repeat this until you get the identity again:
  • put a copy of the array at the end of the list
  • call the method to get next permutation.

• 创建List<int[]>以保存所有排列
• 创建一个大小为 N 的数组并用标识 ({1,2,3,...,N}) 填充它
• 就地创建按字典顺序排列的程序功能
• 重复此操作，直到再次获得身份：
  • 将数组的副本放在列表的末尾
  • 调用该方法以获取下一个排列。

If your program just needs to output all permutations, I would avoid to store them and just print them right away.

如果您的程序只需要输出所有排列，我会避免存储它们并立即打印它们。

The algorithm to compute next permutation can be found on internet. Here for example

计算下一个排列的算法可以在互联网上找到。这里例如

回答by maaartinus

Use whatever you want, arrays or lists, but don't convert them - it just makes it harder. I can't tell what's better, probably I'd go for ArrayList<int[]>, since the outer List allows me to add the permutation easily and the inner array is good enough. That's just a matter of taste (but normally prefer lists, since they're much more flexible).

使用任何你想要的，数组或列表，但不要转换它们 - 它只会让它变得更难。我不知道什么更好，可能我会选择ArrayList<int[]>，因为外部 List 允许我轻松添加排列并且内部数组足够好。这只是品味问题（但通常更喜欢列表，因为它们更灵活）。