全排列算法的全面解析

概述

对数组进行全排列是一个比较常见问题，如果是一个比较喜欢考算法的公司（貌似一些大公司都比较喜欢考算法），那么估计就会考察应聘者这个全排列的问题了（就算不让你编写完整代码，也会让你描述大致的思路）。这个问题也难也难，说易也易，下面我就来对这个问题进行一个比较全面的解析吧。如有遗漏，还望指正。

版权说明

著作权归作者所有。
商业转载请联系作者获得授权，非商业转载请注明出处。
本文作者：Q-WHai
发表日期： 2016年3月27日
本文链接：https://qwhai.blog.csdn.net/article/details/
来源：CSDN
更多内容：分类 >> 算法与数学

描述

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2] 

如果要按从小到大输出呢？算法又要怎么写？

基于递归的实现

思路分析

所有元素均无相同的情况

基于上面的分析，我们知道这个可以采用递归式实现，实现代码如下：

private static void core(int[] array) { 
       int length = array.length; fullArray(array, 0, length - 1); } private static void fullArray(int[] array, int cursor, int end) { 
       if (cursor == end) { 
       System.out.println(Arrays.toString(array)); } else { 
       for (int i = cursor; i <= end; i++) { 
       ArrayUtils.swap(array, cursor, i); fullArray(array, cursor + 1, end); } } } 

运行结果

[1, 2, 3] [1, 3, 2] [3, 1, 2] [3, 2, 1] [1, 2, 3] [1, 3, 2] 

private static void fullArray(int[] array, int cursor, int end) { 
       if (cursor == end) { 
       System.out.println(Arrays.toString(array)); } else { 
       for (int i = cursor; i <= end; i++) { 
       ArrayUtils.swap(array, cursor, i); fullArray(array, cursor + 1, end); ArrayUtils.swap(array, cursor, i); // 用于对之前交换过的数据进行还原 } } } 

修改后的运行结果

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 2, 1] [3, 1, 2] 

存在相同元素的情况

上面的程序乍一看没有任何问题了。可是，如果我们对序列进行一下修改 array = {1, 2, 2}.我们看看运行的结果会怎么样。

[1, 2, 2] [1, 2, 2] [2, 1, 2] [2, 2, 1] [2, 2, 1] [2, 1, 2] 

这里出现了好多的重复。重复的原因当然是因为我们列举了所有位置上的可能性，而没有太多地关注其真实的数值。
现在，我们这样来思考一下，如果有一个序列T = {a1, a2, a3, …, ai, … , aj, … , an}。其中，a[i] = a[j]。那么是不是就可以说，在a[i]上，只要进行一次交换就可以了，a[j]可以直接忽略不计了。好了，基于这样一个思路，我们对程序进行一些改进。我们每一次交换递归之前对元素进行检查，如果这个元素在后面还存在数值相同的元素，那么我们就可以跳过进行下一次循环递归（当然你也可以反着来检查某个元素之前是不是相同的元素）。
基于这个思路，不难写出改进的代码。如下：

private static void core(int[] array) { 
       int length = array.length; fullArray(array, 0, length - 1); } private static boolean swapAccepted(int[] array, int start, int end) { 
       for (int i = start; i < end; i++) { 
       if (array[i] == array[end]) { 
       return false; } } return true; } private static void fullArray(int[] array, int cursor, int end) { 
       if (cursor == end) { 
       System.out.println(Arrays.toString(array)); } else { 
       for (int i = cursor; i <= end; i++) { 
       if (!swapAccepted(array, cursor, i)) { 
       continue; } ArrayUtils.swap(array, cursor, i); fullArray(array, cursor + 1, end); ArrayUtils.swap(array, cursor, i); // 用于对之前交换过的数据进行还原 } } } 

基于非递归的实现

思路分析

由于非递归的方法是基于对元素大小关系进行比较而实现的，所以这里暂时不考虑存在相同数据的情况。
在没有相同元素的情况下，任何不同顺序的序列都不可能相同。不同的序列就一定会有大有小。也就是说，我们只要对序列按照一定的大小关系，找到某一个序列的下一个序列。那从最小的一个序列找起，直到找到最大的序列为止，那么就算找到了所有的元素了。
好了，现在整体思路是清晰了。可是，要怎么找到这里说的下一个序列呢？这个下一个序列有什么性质呢？
T[i]下一个序列T[i+1]是在所有序列中比T[i]大，且相邻的序列。关于怎么找到这个元素，我们还是从一个例子来入手吧。
现在假设序列T[i] = {6, 4, 2, 8, 3, 1}，那么我们可以通过如下两步找到它的下一个序列。

看完上面的两个步骤，不知道大家有没有理解。如果不理解，那么不理解的点可能就在于替换点和被替点的寻找，以及之后为什么又要进行反转上。我们一个一个地解决问题吧。

• 替换点和被替换点的寻找。替换点是从整个序列最后一个位置开始，找到一个连续的上升的两个元素。前一个元素的index就是替换点。再从替换点开始，向后搜寻找到一个只比替换点元素大的被替换点。（如果这里你不是很理解，可以结合图形多思考思考。）
• 替换点后面子序列的反转。在上一步中，可以看到替换之后的子序列（{8, 2, 1}）是一个递减的序列，而替换点又从小元素换成 了大元素，那么与之前序列紧相邻的序列必定是{8, 2, 1}的反序列，即{1, 2, 8}。
  这样，思路已经完全梳理完了，现在就是对其的实现了。只是为了防止给定的序列不是最小的，那就需要对其进行按从小到大进行排序。
  
  

逻辑实现

public class DemoFullArray2 { 
        public static void main(String[] args) { 
        int[] array = { 
       2, 3, 1, 4}; core(array); } private static void core(int[] array) { 
        // 先排序 SortUtils sortUtils = new SortUtils(new QKSort()); sortUtils.sort(array); System.out.println(Arrays.toString(array)); // 最初始的序列 do { 
        nextArray(array); System.out.println(Arrays.toString(array)); } while (!isLast(array)); } private static int[] nextArray(int[] array) { 
        int length = array.length; // 寻找替换点 int cursor = 0; for (int i = length - 1; i >= 1; i--) { 
        // 找到第一个递增的元素对 if (array[i - 1] < array[i]) { 
        cursor = i - 1; // 找到替换点 break; } } // 寻找在替换点后面的次小元素 int biggerCursor = cursor + 1; for (int i = cursor + 1; i < length; i++) { 
        if (array[cursor] < array[i] && array[i] < array[biggerCursor]) { 
        biggerCursor = i; } } // 交换 ArrayUtils.swap(array, cursor, biggerCursor); // 对替换点之后的序列进行反转 reverse(array, cursor); return array; } private static void reverse(int[] array, int cursor) { 
        int end = array.length - 1; for (int i = cursor + 1; i <= end; i++, end--) { 
        ArrayUtils.swap(array, i, end); } } private static boolean isLast(int[] array) { 
        int length = array.length; for (int i = 1; i < length; i++) { 
        if (array[i - 1] < array[i]) { 
        return false; } } return true; } } 

Ref

• http://blog.csdn.net/morewindows/article/details/

征集