在Java中实现置换算法的技巧
|
作为学校项目的一部分，我需要编写一个函数，该函数将使用整数N并返回数组{0，1，...，N-1}的每个排列的二维数组。该声明看起来像公共静态int [] [] permutations（int N）。
http://www.usna.edu/Users/math/wdj/book/node156.html中描述的算法是我决定实现此算法的方式。
我用ArrayLists的数组和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;
}
}
没有找到相关结果
已邀请:
5 个回复
社攻取墟槽
，所以我将直接使用数组。您可以在一开始就以正确的尺寸声明它，并在最后返回它。因此，您完全不必担心以后进行转换。艰管垮淮
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\"); } }弓萍功
。 当心阶乘快速增长：对于N = 13，有13个！排列是6 227 020800。但是我想您只需要为较小的值运行它。 上面的算法非常复杂，我的解决方案是： 创建以容纳所有排列 创建一个大小为N的数组，并用标识填充（{1,2,3，...，N}） 适当的程序功能可按字典顺序创建下一个排列 重复此过程，直到再次获得身份： 将数组的副本放在列表的末尾 调用该方法以获得下一个排列。 如果您的程序只需要输出所有排列，我将避免存储它们并立即打印它们。 可以在互联网上找到计算下一个排列的算法。例如这里讼乐
藕挝
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; }