数组的排列

例如,我有这个数组:

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函数很好,但是对我来说并没有太大的帮助。

如果您使用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)); 

以下是如何在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个排列。

以下是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); } } } 

这是一个包含在迭代器中的列表的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() { } } 

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]] 

希望这可以帮助。

基本数组的例子:

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

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

分解:

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

一个简单的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; } }