在Java中实现置换算法的技巧
作为学校项目的一部分，我需要编写一个函数，该函数将采用整数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 = N) { d *= -1; j += d; } } return permutations; } } 那么将它移植到Java的最佳策略是什么？ 我可以用原始数组来做吗？ 我需要一个ArrayLists数组吗？ 或ArrayLists的ArrayList？ 或者是否有其他数据类型更好？ 无论我使用什么，我都需要能够将它转换回一个原始数组的数组。
也许有一个更好的算法可以简化这个…
提前感谢您的建议！
如你所知，预先排列的数量（它是N！），你也想要/必须返回一个int[][]我会直接找到一个数组。 您可以在开头用正确的尺寸声明它并在最后返回它。 因此，您根本不必担心之后转换它。
因为你几乎已经在javascript中自己完成了它，所以我将继续为你提供实现Steinhaus排列算法的Java代码。 我基本上只是将您的代码移植到Java，尽可能多地保留它，包括注释。
我测试了N = 7.我试着让它计算N = 8，但它已经在2 GHz Intel Core 2 Duo处理器上运行了差不多10分钟，但仍在继续，哈哈。
我敢肯定，如果你真的在这方面工作，你可以大大提高速度，但即便如此，你可能只能从中挤出更多的N值，除非你当然可以访问超级计算机;-)。
警告 – 此代码是正确的，不健全。 如果你需要它很强大，你通常不需要做家庭作业，那么这将是一个留给你的练习。 我还建议使用Java Collections实现它，因为它是学习Collections API的输入和输出的好方法。
有几个“辅助”方法，包括一个打印二维数组。 请享用！
更新：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"); } }
java数组不可变（从某种意义上说，你不能改变它们的长度）。 对于这种递归算法的直接转换，您可能希望使用List接口（可能还有LinkedList实现，因为您希望将数字放在中间）。 那就是List 。
谨防因子迅速增长：对于N = 13，有13个！ 排列是6 227 020 800.但我猜你需要只为小值运行它。
上面的算法非常复杂，我的解决方案是：
- 创建
List以保存所有排列 - 创建一个大小为N的数组并用身份填充它（{1,2,3，…，N}）
- 程序function，在字典顺序中创建下一个排列
- 重复这个，直到你再次获得身份：
- 将数组的副本放在列表的末尾
- 调用该方法以获得下一个排列。
如果您的程序只需要输出所有排列，我会避免存储它们并立即打印它们。
计算下一个排列的算法可以在互联网上找到。 这里举个例子
使用你想要的任何东西，数组或列表，但不要转换它们 – 它只会使它变得更难。 我不知道什么是更好的，可能我会选择ArrayList ，因为外部List允许我轻松添加排列，内部数组足够好。 这只是一个品味问题（但通常更喜欢列表，因为它们更灵活）。
根据霍华德的建议，我决定除了原始数组类型之外我不想使用任何东西。 我最初选择的算法很难在Java中实现，所以感谢跟踪者的建议，我选择了维基百科中描述的词典排序算法 。 这就是我最终得到的结果：
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 < Nj; j++) swap(a[i], k+j, Nj); } 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; }