打印出数组的所有排列
我正在研究一个程序，我有一个函数可以交换用户输入的长度数组中的位置。 但是，我想弄清楚如何打印出这个函数调用N！ times，列出函数中的所有排列。
我的置换函数代码是：
static void nextPerm(int[] A){ for( int i = (n-1); i > 0; i-- ){ if( A[i] = A[i+1] ){ reverseArray(A); return; } } for( int i = n; i > 0; i--){ if( A[i] > pivot ){ A[i] = successor; continue; } } Swap(pivot, successor); int[] B = new int[pivot+1]; reverseArray(B); return; } 我应该在函数main中写一个循环，这将打印出来！ 次？
创建（或打印）数组的排列作为递归和迭代的组合比纯粹迭代地更容易完成。 肯定有迭代方法可以实现，但组合起来却特别简单。 具体来说，注意根据定义N！ 长度为Narrays的排列 – 第一个槽的N个选择，第二个槽的N-1个选择等等。因此， 对于arrays中的每个索引i ，我们可以将算法分解为两个步骤。
- 选择子数组
arr[i....end]中的元素作为数组的ith元素。 用当前在arr[i]的元素交换该元素。 - 递归地置换
arr[i+1...end]。
我们注意到这将在O（N！）中运行，因为在第一次调用时将进行N个子调用，每个调用将进行N-1个子调用等。此外，每个元素最终都会在每个位置，只要只进行交换，就不会复制任何元素。
public static void permute(int[] arr){ permuteHelper(arr, 0); } private static void permuteHelper(int[] arr, int index){ if(index >= arr.length - 1){ //If we are at the last element - nothing left to permute //System.out.println(Arrays.toString(arr)); //Print the array System.out.print("["); for(int i = 0; i < arr.length - 1; i++){ System.out.print(arr[i] + ", "); } if(arr.length > 0) System.out.print(arr[arr.length - 1]); System.out.println("]"); return; } for(int i = index; i < arr.length; i++){ //For each index in the sub array arr[index...end] //Swap the elements at indices index and i int t = arr[index]; arr[index] = arr[i]; arr[i] = t; //Recurse on the sub array arr[index+1...end] permuteHelper(arr, index+1); //Swap the elements back t = arr[index]; arr[index] = arr[i]; arr[i] = t; } }
样本输入，输出：
public static void main(String[] args) { permute(new int[]{1,2,3,4}); } [1, 2, 3, 4] [1, 2, 4, 3] [1, 3, 2, 4] [1, 3, 4, 2] [1, 4, 3, 2] [1, 4, 2, 3] [2, 1, 3, 4] [2, 1, 4, 3] [2, 3, 1, 4] [2, 3, 4, 1] [2, 4, 3, 1] [2, 4, 1, 3] [3, 2, 1, 4] [3, 2, 4, 1] [3, 1, 2, 4] [3, 1, 4, 2] [3, 4, 1, 2] [3, 4, 2, 1] [4, 2, 3, 1] [4, 2, 1, 3] [4, 3, 2, 1] [4, 3, 1, 2] [4, 1, 3, 2] [4, 1, 2, 3]
我大部分时间都遵循这种方法..（由Robert Sedgewick和Kevin Wayne提供）。
public class Permutations { // print N! permutation of the characters of the string s (in order) public static void perm1(String s) { perm1("", s); } private static void perm1(String prefix, String s) { int N = s.length(); if (N == 0) System.out.println(prefix); else { for (int i = 0; i < N; i++) perm1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N)); } } // print N! permutation of the elements of array a (not in order) public static void perm2(String s) { int N = s.length(); char[] a = new char[N]; for (int i = 0; i < N; i++) a[i] = s.charAt(i); perm2(a, N); } private static void perm2(char[] a, int n) { if (n == 1) { System.out.println(a); return; } for (int i = 0; i < n; i++) { swap(a, i, n-1); perm2(a, n-1); swap(a, i, n-1); } } // swap the characters at indices i and j private static void swap(char[] a, int i, int j) { char c; c = a[i]; a[i] = a[j]; a[j] = c; }
但是，还有一种更简单的方法可以做到这一点。 也许你可以在这周围工作
class PermutingArray { static void permutingArray(java.util.List arrayList, int element) { for (int i = element; i < arrayList.size(); i++) { java.util.Collections.swap(arrayList, i, element); permutingArray(arrayList, element + 1); java.util.Collections.swap(arrayList, element, i); } if (element == arrayList.size() - 1) { System.out.println(java.util.Arrays.toString(arrayList.toArray())); } } public static void main(String[] args) { PermutingArray .permutingArray(java.util.Arrays.asList(9, 8, 7, 6, 4), 0); } }
这里的工作示例.. IDeone链接
诀窍是当nextPerm是最后一个排列时（即当数组按降序排序时）从nextPerm返回一个特殊值（在下面的代码中为false ）：
import java.util.*; public class Main { public static boolean nextPerm(List a) { int i = a.size() - 2; while (i >= 0 && a.get(i) >= a.get(i + 1)) i--; if (i < 0) return false; int j = a.size() - 1; while (a.get(i) >= a.get(j)) j--; Collections.swap(a, i, j); Collections.reverse(a.subList(i + 1, a.size())); return true; } ...
然后你可以使用循环（注意所需的数组最初按升序排序）：
... public static void main(String[] args) { List a = Arrays.asList(new Integer[] {1, 2, 3, 4}); do { System.out.println(a); } while (nextPerm(a)); } }
您可以在此处试用此代码： http ： //ideone.com/URDFsc