关键词：
概述
对数组进行全排列是一个比较常见问题，如果是一个比较喜欢考算法的公司（貌似一些大公司都比较喜欢考算法），那么估计就会考察应聘者这个全排列的问题了（就算不让你编写完整代码，也会让你描述大致的思路）。这个问题也难也难，说易也易，下面我就来对这个问题进行一个比较全面的解析吧。如有遗漏，还望指正。
版权说明
著作权归作者所有。
商业转载请联系作者获得授权，非商业转载请注明出处。
本文作者：Q-WHai
发表日期： 2016年3月27日
本文链接：https://qwhai.blog.csdn.net/article/details/50986990
来源：CSDN
更多内容：分类 >> 算法与数学
描述
对于一个给定的序列 a = [a1, a2, a3, … , an]，请设计一个算法，用于输出这个序列的全部排列方式。
例如：a = [1, 2, 3]
输出
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
如果要按从小到大输出呢？算法又要怎么写？
基于递归的实现
思路分析
我们知道全排列的含义就是一个序列所有的排序可能性，那么我们现在做这样的一个假设，假设给定的一些序列中第一位都不相同，那么就可以认定说这些序列一定不是同一个序列，这是一个很显然的问题。有了上面的这一条结论，我们就可以同理得到如果在第一位相同，可是第二位不同，那么在这些序列中也一定都不是同一个序列，这是由上一条结论可以获得的。
那么，这个问题可以这样来看。我们获得了在第一个位置上的所有情况之后，抽去序列T中的第一个位置，那么对于剩下的序列可以看成是一个全新的序列T1，序列T1可以认为是与之前的序列毫无关联了。同样的，我们可以对这个T1进行与T相同的操作，直到T中只一个元素为止。这样我们就获得了所有的可能性。所以很显然，这是一个递归算法。
例如下面这幅图，就是第1个元素与其后面的所有其他元素进行交换的示意图。
如果我们从中抽出第i个元素，将剩下的其余元素进行上图交换操作，将是如下示意图。
所有元素均无相同的情况
基于上面的分析，我们知道这个可以采用递归式实现，实现代码如下：
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]
这个答案就有一些让人匪夷所思了，为什么会有几组是重复的？为什么第一位里面没有 2？
理论上，上面的代码没有问题，因为当我们循环遍历序列中每一位时，都有继续进行后面序列的递归操作。core()方法当然没什么问题，问题是出在fullArray()方法上了。很容易锁定在了那个for循环里。我们来仔细推敲一下循环体里的代码，当我们对序列进行交换之后，就将交换后的序列除去第一个元素放入到下一次递归中去了，递归完成了再进行下一次循环。这是某一次循环程序所做的工作，这里有一个问题，那就是在进入到下一次循环时，序列是被改变了。可是，如果我们要假定第一位的所有可能性的话，那么，就必须是在建立在这些序列的初始状态一致的情况下（感兴趣的你可以想想这是为什么）。
好了，这样一来问题找到了，我们需要保证序列进入下一次循环时状态的一致性。而保证的方式就是对序列进行还原操作。我们修改fullArray()如下：
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/7370155
征集
如果你也需要使用ProcessOn这款在线绘图工具，可以使用如下邀请链接进行注册：
https://www.processon.com/i/56205c2ee4b0f6ed10838a6d
数据结构与算法之深入解析n个数全排列的求解思路与算法示例(代码片段)
一、全排列I①题目描述给定一个不含重复数字，长度为N的数组nums，返回其所有可能的全排列，可以按任意顺序返回结果。示例1：输入：nums=[1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例2：... 查看详情
常见的算法问题全排列(代码片段)
...采用暴力破解所以这个时候我就想进行一下总结：关于全排列问题的通用解法，比如：（无重复全排列）（有重复的选取）（从N个数中选取m个数然后进行排列的问题）我这里尝试总结一下：比如一般问题喜欢问1-9有多少种全排... 查看详情
算法设计：全排列算法代码实现(代码片段)
在上星期的算法设计课程的学习中，我们学习了两种全排列算法，该算法用于求出数组1,2,3,...,n的所有可能的排列，今天我们就来看看这个算法的具体代码实现。 1. 第一种算法第一种算法和我们现实生活中习惯的方法较... 查看详情
算法习题---字符串的全排序列(代码片段)
一：什么是全排列排列：从n个元素中任取m个元素，并按照一定的顺序进行排列，称为排列；全排列：当n==m时，称为全排列；比如：集合1,2,3的全排列为：123132213231321312我们可以将这个排列问题画成图形表示，即排列枚举树，比... 查看详情
全排列算法（递归）(代码片段)
全排列算法是一种经典的递归算法。例如集合a，b，c的全排列为（a，b，c）、（a，c，b）、（b，a，c）、（b，c，a）、（c，b，a）、（c，a，b）共3！种。 递归法求解的思路是先固定第一个元素，求剩下的全排列，求剩... 查看详情
全排列算法实现(代码片段)
7年前一个组合算法错失鹅场offer，之后专门了解排列组合的算法，岂知入了社会，大部分算法根本就用不到。闲着无事，回忆排列算法如何实现的。算法最重要的一步-证明，貌似一般学校都不教的吧。用数学归纳可以简单认为... 查看详情
java与算法之-数字全排列(代码片段)
全排列是指n个数(或其他字符)所有可能的排列顺序，例如123三个数字的全排列是123132213231312321那么问题来了，任意输入一个大于1的数字n，列出1-n这n个数字的全排列。如果尝试手动列举一下123的全排列，会发现通常我们会在头脑... 查看详情
字符串去反复全排列算法(代码片段)
...写叙述】输入一个字符串，打印出该字符串中字符的全部排列。比如输入字符串abc，则输出由字符a、b、c所能排列出来的全部字符串abc、acb、bac、bca、cab和cba。【分析】从集合中依次选出每个元素。作为排列的第一个元素，然后... 查看详情
算法问题寻找全排列的下一个数(代码片段)
寻找全排列的下一个数摘自漫画算法：题目：给出一个正整数，找出这个正整数所有数字全排列的下一个树。说的通俗点就是在一个整数所包含数字的全部组合中，找到一个大于且仅大于原数的新整数。例子：如果输入12345，则... 查看详情
算法问题寻找全排列的下一个数(代码片段)
寻找全排列的下一个数摘自漫画算法：题目：给出一个正整数，找出这个正整数所有数字全排列的下一个树。说的通俗点就是在一个整数所包含数字的全部组合中，找到一个大于且仅大于原数的新整数。例子：如果输入12345，则... 查看详情
全排列(代码片段)
全排列回溯算法之排列树一问题描述给出一串字符的全排列二问题分析采用回溯算法之排列树三代码实现packagebacktracking_perm;importjava.io.BufferedWriter;importjava.io.FileWriter;importjava.io.IOException;importjava.util.Arrays;importjava.util.LinkedList 查看详情
全排列算法实现(代码片段)
全排列算法实现方法1：插入法，取字符串的第一个元素放到集合res，后面将字符串的其余元素依次插入到当前集合res的前，中，后。importjava.util.ArrayList;publicclassFullPermutation1publicstaticArrayList<String>f(Strings)Ar 查看详情
算法9-----输出全排列（递归）(代码片段)
...cca‘]2、递归：如：‘abc‘，对于‘a‘，返回’bc‘的全排列字典序，对于‘b‘，返回‘ac‘的全排列，对于‘c‘，返回‘ab‘的全排 查看详情
全排列递归实现
前面我们介绍了全排列的非递归算法，现在我再来写一下全排列的递归算法：这两种算法的算法思路并不相同。递归算法的思路比较接近于我们现实生活中的思路。1.试想，我们只有两个数字：12.要对它进行全排列，第一种方式... 查看详情
全排列(代码片段)
详细解答看C++输出全排列递归算法详细解释假设数组含有n个元素，则提取数组中的每一个元素做一次头元素，然后全排列除数组中除第一个元素之外的所有元素，这样就达到了对数组中所有元素进行全排列的得目的。比如1，2，... 查看详情
最强解析面试题：字符串全排列「建议收藏！」(代码片段)
文章目录最强解析面试题：字符串全排列「建议收藏！」题目示例1思路代码附录最强解析面试题：字符串全排列「建议收藏！」文章讲解“字符串全排列”经典面试题，包含思路及源码，及解惑！题目... 查看详情
最强解析面试题：字符串全排列「建议收藏！」(代码片段)
文章目录最强解析面试题：字符串全排列「建议收藏！」题目示例1思路代码附录最强解析面试题：字符串全排列「建议收藏！」文章讲解“字符串全排列”经典面试题，包含思路及源码，及解惑！题目... 查看详情
leetcode-46.全排列--回溯算法--python(代码片段)
全排列问题使用回溯算法解决思路：定义res列表存放最后的结果定义track列表构建排列存放每次的排列在backtrack函数中，for循环中1.满足条件，加入res，2.做选择：track.append(nums[i])3.回溯函数：backtrack(nums,trac... 查看详情