在Java中实现排列算法的技巧

Question

作为学校项目的一部分，我需要编写一个函数，该函数将接收一个整数N并返回数组{0, 1, ..., N-1}的每个排列的二维数组。声明应如下所示：public static int[][] permutations(int N)。

我决定按照http://www.usna.edu/Users/math/wdj/book/node156.html中描述的算法进行实现。

我曾尝试使用数组和数组列表的组合，以及数组列表的嵌套，但是到目前为止，我一直被困扰，特别是在尝试将二维数组列表转换为二维数组时。

因此，我用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的最佳策略是什么？我能只使用原始数组吗？我需要一个ArrayList数组还是ArrayList的ArrayList？或者有其他更好的数据类型吗？无论我使用什么，我需要能够将其转换回原始数组。

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

提前感谢您的建议！

- Trevor Dixon

---

allPermutations(1)会递归直到发生StackOverflow。 - rsp

我也过着那样的生活。祝你好运，兄弟。 - Lpc_dark

Answer 1

正如您所知道的，排列的数量是预先确定的（它是 N!），并且您想要/必须返回一个 int[][]，我建议直接使用数组。您可以在开头正确地声明它的维度，并在结尾处返回它。这样，您就不必担心之后的转换问题。

- Howard

Answer 2

既然你已经在javascript中几乎完成了它，那么我将提供实现Steinhaus排列算法的Java代码。我基本上只是将你的代码移植到了Java中，尽可能保留了它的原貌，包括注释。

我测试了N = 7。我试图让它计算N = 8，但它已经在2 GHz英特尔Core 2 Duo处理器上运行了将近10分钟，还在继续，哈哈。

我相信如果你真的努力去做，你可以显著加快它的速度，但即使这样，你可能只能从中挤出几个N值，除非当然你有超级计算机的访问权限;-)。

警告-此代码是正确的，但不是稳健的。如果您需要它稳健，通常不需要为作业任务，那么这将成为您的练习。我还建议使用Java集合来实现它，因为这将是学习集合API的好方法。

包括一个打印2D数组的“helper”方法。享受吧！

更新：N = 8花费了25分钟38秒。

编辑：修复了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");
  }
}

- user711807

Answer 3

Java数组是不可变的（即您无法更改它们的长度）。对于这个递归算法的直接翻译，您可能想使用List接口（并且可能要使用LinkedList实现，因为您想将数字放在中间）。那就是List<List<Integer>>。

请注意，阶乘增长迅速：对于N = 13，有13！排列，即6,227,020,800。但我猜您只需要运行它以获取小值。

上面的算法非常复杂，我的解决方案是：

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

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

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

- stalker

---

好建议；那几乎就是我最终要做的事情了。我发现在Java中实现词典算法要容易得多。非常感谢！ - Trevor Dixon

Answer 4

根据Howard的建议，我决定除了原始数组类型以外不使用其他任何东西。最初选择的算法在Java中实现起来很痛苦，所以感谢stalker的建议，我采用了维基百科描述的字典序排序算法。这是我的最终结果：

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

- Trevor Dixon

Answer 5

使用任何你想用的，数组或列表，但不要转换它们 - 这只会让它更难。我无法确定哪个更好，可能我会选择 ArrayList<int[]>，因为外部 List 允许我轻松添加排列，而内部数组已经足够好了。这只是一种口味问题（但通常更喜欢列表，因为它们更加灵活）。

- maaartinus