简介：
本文主要介绍基于分治方式（递归）和枚举方式（循环）来构建指定字符串的全排列方法，两种方法都可以解决重复元素的全排列
欢迎探讨，如有错误敬请指正
如需转载，请注明出处 http://www.cnblogs.com/nullzx/
1. 基于分治方式（递归实现）
1）一个元素的全排列只有一种
2）[A0, A1, A2]的全排列等于下面三个全排列的并集
A0开头，拼接上[A1,A2]的所有全排列
A1开头，拼接上[A0,A2]的所有全排列
A2开头，拼接上[A0,A1]的所有全排列
所以，对于[A0, A1, ……，An]的全排列，我们可以将问题转换成n个子问题：
A0开头，拼接上[A1,A2 ……，An]的所有全排列
A1开头，拼接上[A0,A2 ……，An]的所有全排列
……
An开头，拼接上[A0,A2 ……，A(n-1)]的所有全排列
而每个子问题又可以继续向下转化成n-1个子问题，最终可以转化到只有一个元素的全排列问题。
对于数组中有重复元素的情况，我们只要保证，重复元素只能有一次作为子问题的开头元素，这样我们就可以避免重复计算。
2. 基于枚举方式（循环实现）
如果我们将全排列按照大小顺序进行排序，假设我们知道了第i个排列是[A0, A1, A2, A3, ……]，那么第i+1个排列就是比[A0, A1, A2, A3, ……]大，且最小的那个。找到i+1个排列的步骤如下
1）从后往前两两比较，找到第一个满足a[i]<a[i+1]的两个元素
2）从a[i+1]开始往后找，找到一个大于a[i]中最小的一个元素,这个元素的下标记为j，交换a[i]和a[j]
3）将[i+1, a.length-1]的元素全部逆序
笔者只理解了第一种方法
转播
