数组的排列

例如，我有这个数组：

int a[] = new int[]{3,4,6,2,1}; 

我需要列出所有的排列，如果这样的话， {3,2,1,4,6} ，其他的不能相同。 我知道，如果数组的长度是n，那么就有n！ 可能的组合。 这个算法怎么写？

更新：谢谢，但我需要一个伪代码算法，如：

 for(int i=0;i<a.length;i++){ // code here } 

只是算法。 是的，API函数很好，但是对我来说并没有太大的帮助。

Answer 1

如果您使用C ++，则可以使用算法头中的std :: next_permutation：

 int a[] = {3,4,6,2,1}; int size = sizeof(a)/sizeof(a[0]); std::sort(a, a+size); do { // print a's elements } while(std::next_permutation(a, a+size)); 

Answer 2

以下是如何在10行代码中打印所有排列：

 public class Permute{ static void permute(java.util.List<Integer> arr, int k){ for(int i = k; i < arr.size(); i++){ java.util.Collections.swap(arr, i, k); permute(arr, k+1); java.util.Collections.swap(arr, k, i); } if (k == arr.size() -1){ System.out.println(java.util.Arrays.toString(arr.toArray())); } } public static void main(String[] args){ Permute.permute(java.util.Arrays.asList(3,4,6,2,1), 0); } } 

你取一个数组（k = 0）的第一个元素，并与数组中的任何元素（i）进行交换。 然后你递归地应用排列从第二个元素开始的数组。 这样你就可以得到从第i个元素开始的所有排列。 棘手的部分是，在递归调用之后，您必须将第i个元素与第一个元素交换回来，否则您可能会在第一个位置获得重复的值。 通过交换它，我们恢复元素的顺序（基本上你会回溯）。

迭代器和扩展到重复值的情况

以前的算法的缺点是它是递归的，并不能很好地与迭代器一起玩。 另一个问题是，如果您在输入中允许重复的元素，那么它将不会按原样工作。

例如，给定输入[3,3,4,4]的所有可能的排列（没有重复）是

 [3, 3, 4, 4] [3, 4, 3, 4] [3, 4, 4, 3] [4, 3, 3, 4] [4, 3, 4, 3] [4, 4, 3, 3] 

（如果你只是从上面应用permute函数，你会得到[3,3,4,4]四次，这不是你自然想要在这种情况下看到的;这样的置换的数目是4！/（2 ！* 2！）= 6）

可以修改上面的算法来处理这种情况，但是看起来不太好。 幸运的是，有一个更好的算法（我发现它在这里 ）处理重复的值，而不是递归的。

首先要注意的是，任何对象数组的排列可以通过按任意顺序枚举来简化为整数的排列。

要获得整数数组的排列，可以按照升序排列的数组开始。 你的目标是让它下降。 为了生成下一个排列，你试图找到序列不能下降的底部的第一个索引，并且改进该索引中的值，同时在这种情况下将尾部的其余部分的顺序从下降切换到上升。

这是算法的核心：

 //ind is an array of integers for(int tail = ind.length - 1;tail > 0;tail--){ if (ind[tail - 1] < ind[tail]){//still increasing //find last element which does not exceed ind[tail-1] int s = ind.length - 1; while(ind[tail-1] >= ind[s]) s--; swap(ind, tail-1, s); //reverse order of elements in the tail for(int i = tail, j = ind.length - 1; i < j; i++, j--){ swap(ind, i, j); } break; } } 

这里是迭代器的完整代码。 构造函数接受一个对象数组，并使用HashMap将其映射到一个整数数组中。

 import java.lang.reflect.Array; import java.util.*; class Permutations<E> implements Iterator<E[]>{ private E[] arr; private int[] ind; private boolean has_next; public E[] output;//next() returns this array, make it public Permutations(E[] arr){ this.arr = arr.clone(); ind = new int[arr.length]; //convert an array of any elements into array of integers - first occurrence is used to enumerate Map<E, Integer> hm = new HashMap<E, Integer>(); for(int i = 0; i < arr.length; i++){ Integer n = hm.get(arr[i]); if (n == null){ hm.put(arr[i], i); n = i; } ind[i] = n.intValue(); } Arrays.sort(ind);//start with ascending sequence of integers //output = new E[arr.length]; <-- cannot do in Java with generics, so use reflection output = (E[]) Array.newInstance(arr.getClass().getComponentType(), arr.length); has_next = true; } public boolean hasNext() { return has_next; } /** * Computes next permutations. Same array instance is returned every time! * @return */ public E[] next() { if (!has_next) throw new NoSuchElementException(); for(int i = 0; i < ind.length; i++){ output[i] = arr[ind[i]]; } //get next permutation has_next = false; for(int tail = ind.length - 1;tail > 0;tail--){ if (ind[tail - 1] < ind[tail]){//still increasing //find last element which does not exceed ind[tail-1] int s = ind.length - 1; while(ind[tail-1] >= ind[s]) s--; swap(ind, tail-1, s); //reverse order of elements in the tail for(int i = tail, j = ind.length - 1; i < j; i++, j--){ swap(ind, i, j); } has_next = true; break; } } return output; } private void swap(int[] arr, int i, int j){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public void remove() { } } 

用法/测试：

  TCMath.Permutations<Integer> perm = new TCMath.Permutations<Integer>(new Integer[]{3,3,4,4,4,5,5}); int count = 0; while(perm.hasNext()){ System.out.println(Arrays.toString(perm.next())); count++; } System.out.println("total: " + count); 

打印全部7!/(2!*3!*2!)=210个排列。

Answer 3

以下是Java中的排列实现：

排列 – Java

你应该检查它！

编辑：代码粘贴下面，以防止链接死亡：

 // Permute.java -- A class generating all permutations import java.util.Iterator; import java.util.NoSuchElementException; import java.lang.reflect.Array; public class Permute implements Iterator { private final int size; private final Object [] elements; // copy of original 0 .. size-1 private final Object ar; // array for output, 0 .. size-1 private final int [] permutation; // perm of nums 1..size, perm[0]=0 private boolean next = true; // int[], double[] array won't work :-( public Permute (Object [] e) { size = e.length; elements = new Object [size]; // not suitable for primitives System.arraycopy (e, 0, elements, 0, size); ar = Array.newInstance (e.getClass().getComponentType(), size); System.arraycopy (e, 0, ar, 0, size); permutation = new int [size+1]; for (int i=0; i<size+1; i++) { permutation [i]=i; } } private void formNextPermutation () { for (int i=0; i<size; i++) { // i+1 because perm[0] always = 0 // perm[]-1 because the numbers 1..size are being permuted Array.set (ar, i, elements[permutation[i+1]-1]); } } public boolean hasNext() { return next; } public void remove() throws UnsupportedOperationException { throw new UnsupportedOperationException(); } private void swap (final int i, final int j) { final int x = permutation[i]; permutation[i] = permutation [j]; permutation[j] = x; } // does not throw NoSuchElement; it wraps around! public Object next() throws NoSuchElementException { formNextPermutation (); // copy original elements int i = size-1; while (permutation[i]>permutation[i+1]) i--; if (i==0) { next = false; for (int j=0; j<size+1; j++) { permutation [j]=j; } return ar; } int j = size; while (permutation[i]>permutation[j]) j--; swap (i,j); int r = size; int s = i+1; while (r>s) { swap(r,s); r--; s++; } return ar; } public String toString () { final int n = Array.getLength(ar); final StringBuffer sb = new StringBuffer ("["); for (int j=0; j<n; j++) { sb.append (Array.get(ar,j).toString()); if (j<n-1) sb.append (","); } sb.append("]"); return new String (sb); } public static void main (String [] args) { for (Iterator i = new Permute(args); i.hasNext(); ) { final String [] a = (String []) i.next(); System.out.println (i); } } } 

Answer 4

这是一个包含在迭代器中的列表的2列

 import java.util.Iterator; import java.util.LinkedList; import java.util.List; /* all permutations of two objects * * for ABC: AB AC BA BC CA CB * * */ public class ListPermutation<T> implements Iterator { int index = 0; int current = 0; List<T> list; public ListPermutation(List<T> e) { list = e; } public boolean hasNext() { return !(index == list.size() - 1 && current == list.size() - 1); } public List<T> next() { if(current == index) { current++; } if (current == list.size()) { current = 0; index++; } List<T> output = new LinkedList<T>(); output.add(list.get(index)); output.add(list.get(current)); current++; return output; } public void remove() { } } 

Answer 5

有n! 给定数组大小n全部置换。 这里是用Java编写的使用DFS的代码。

 public List<List<Integer>> permute(int[] nums) { List<List<Integer>> results = new ArrayList<List<Integer>>(); if (nums == null || nums.length == 0) { return results; } List<Integer> result = new ArrayList<>(); dfs(nums, results, result); return results; } public void dfs(int[] nums, List<List<Integer>> results, List<Integer> result) { if (nums.length == result.size()) { List<Integer> temp = new ArrayList<>(result); results.add(temp); } for (int i=0; i<nums.length; i++) { if (!result.contains(nums[i])) { result.add(nums[i]); dfs(nums, results, result); result.remove(result.size() - 1); } } } 

对于输入数组[3,2,1,4,6]，总共有5个！ = 120个可能的排列组合：

 [[3,4,6,2,1],[3,4,6,1,2],[3,4,2,6,1],[3,4,2,1,6],[3,4,1,6,2],[3,4,1,2,6],[3,6,4,2,1],[3,6,4,1,2],[3,6,2,4,1],[3,6,2,1,4],[3,6,1,4,2],[3,6,1,2,4],[3,2,4,6,1],[3,2,4,1,6],[3,2,6,4,1],[3,2,6,1,4],[3,2,1,4,6],[3,2,1,6,4],[3,1,4,6,2],[3,1,4,2,6],[3,1,6,4,2],[3,1,6,2,4],[3,1,2,4,6],[3,1,2,6,4],[4,3,6,2,1],[4,3,6,1,2],[4,3,2,6,1],[4,3,2,1,6],[4,3,1,6,2],[4,3,1,2,6],[4,6,3,2,1],[4,6,3,1,2],[4,6,2,3,1],[4,6,2,1,3],[4,6,1,3,2],[4,6,1,2,3],[4,2,3,6,1],[4,2,3,1,6],[4,2,6,3,1],[4,2,6,1,3],[4,2,1,3,6],[4,2,1,6,3],[4,1,3,6,2],[4,1,3,2,6],[4,1,6,3,2],[4,1,6,2,3],[4,1,2,3,6],[4,1,2,6,3],[6,3,4,2,1],[6,3,4,1,2],[6,3,2,4,1],[6,3,2,1,4],[6,3,1,4,2],[6,3,1,2,4],[6,4,3,2,1],[6,4,3,1,2],[6,4,2,3,1],[6,4,2,1,3],[6,4,1,3,2],[6,4,1,2,3],[6,2,3,4,1],[6,2,3,1,4],[6,2,4,3,1],[6,2,4,1,3],[6,2,1,3,4],[6,2,1,4,3],[6,1,3,4,2],[6,1,3,2,4],[6,1,4,3,2],[6,1,4,2,3],[6,1,2,3,4],[6,1,2,4,3],[2,3,4,6,1],[2,3,4,1,6],[2,3,6,4,1],[2,3,6,1,4],[2,3,1,4,6],[2,3,1,6,4],[2,4,3,6,1],[2,4,3,1,6],[2,4,6,3,1],[2,4,6,1,3],[2,4,1,3,6],[2,4,1,6,3],[2,6,3,4,1],[2,6,3,1,4],[2,6,4,3,1],[2,6,4,1,3],[2,6,1,3,4],[2,6,1,4,3],[2,1,3,4,6],[2,1,3,6,4],[2,1,4,3,6],[2,1,4,6,3],[2,1,6,3,4],[2,1,6,4,3],[1,3,4,6,2],[1,3,4,2,6],[1,3,6,4,2],[1,3,6,2,4],[1,3,2,4,6],[1,3,2,6,4],[1,4,3,6,2],[1,4,3,2,6],[1,4,6,3,2],[1,4,6,2,3],[1,4,2,3,6],[1,4,2,6,3],[1,6,3,4,2],[1,6,3,2,4],[1,6,4,3,2],[1,6,4,2,3],[1,6,2,3,4],[1,6,2,4,3],[1,2,3,4,6],[1,2,3,6,4],[1,2,4,3,6],[1,2,4,6,3],[1,2,6,3,4],[1,2,6,4,3]] 

希望这可以帮助。

Answer 6

基本数组的例子：

 public static void permute(int[] intArray, int start) { for(int i = start; i < intArray.length; i++){ int temp = intArray[start]; intArray[start] = intArray[i]; intArray[i] = temp; permute(intArray, start + 1); intArray[i] = intArray[start]; intArray[start] = temp; } if (start == intArray.length - 1) { System.out.println(java.util.Arrays.toString(intArray)); } } public static void main(String[] args){ int intArr[] = {1, 2, 3}; permute(intArr, 0); } 

Answer 7

三项递归解决方案的可视化表示形式： http : //www.docdroid.net/ea0s/generatepermutations.pdf.html

分解：

1. 对于两个项目的数组，有两个排列组合：
   • 原始数组，和
   • 两个元素交换
2. 对于三项数组，有六个排列组合：
   • 然后，底部两个元素的排列
   • 交换第一项和第二项，以及底部两个元素的排列
   • 交换第一项和第三项，以及底部两个元素的排列。
   • 基本上，每个项目都有机会在第一个位置

Answer 8

一个简单的java实现，请参阅c ++ std::next_permutation ：

 public static void main(String[] args){ int[] list = {1,2,3,4,5}; List<List<Integer>> output = new Main().permute(list); for(List result: output){ System.out.println(result); } } public List<List<Integer>> permute(int[] nums) { List<List<Integer>> list = new ArrayList<List<Integer>>(); int size = factorial(nums.length); // add the original one to the list List<Integer> seq = new ArrayList<Integer>(); for(int a:nums){ seq.add(a); } list.add(seq); // generate the next and next permutation and add them to list for(int i = 0;i < size - 1;i++){ seq = new ArrayList<Integer>(); nextPermutation(nums); for(int a:nums){ seq.add(a); } list.add(seq); } return list; } int factorial(int n){ return (n==1)?1:n*factorial(n-1); } void nextPermutation(int[] nums){ int i = nums.length -1; // start from the end while(i > 0 && nums[i-1] >= nums[i]){ i--; } if(i==0){ reverse(nums,0,nums.length -1 ); }else{ // found the first one not in order int j = i; // found just bigger one while(j < nums.length && nums[j] > nums[i-1]){ j++; } //swap(nums[i-1],nums[j-1]); int tmp = nums[i-1]; nums[i-1] = nums[j-1]; nums[j-1] = tmp; reverse(nums,i,nums.length-1); } } // reverse the sequence void reverse(int[] arr,int start, int end){ int tmp; for(int i = 0; i <= (end - start)/2; i++ ){ tmp = arr[start + i]; arr[start + i] = arr[end - i]; arr[end - i ] = tmp; } }