全排列算法（不含重复元素，包含重复元素，字母序排列）
在某些和组合数学有关的背景下，会需要生成全排列一类的数据集合。而生成全排列，最常用的有以下两种算法。
recursive generating
这个算法接受一个元素均不同的数组，通过递归的调用以生成所有全排列序列。
递归的原则在于，生成序列的全排列P(a1,a2,…,an)等价于生成序列（下面的理解很重要！！）
…
这构成了递归算法设计的deduction-case；而base-case，则是要生成全排列的序列只有一个元素。
整个算法大致上可以如下实现：
void GenePermu(int A[], int i, int n)
{
if (i == n-1)
{
for (int k = 0;
k < n;
++k)
{
cout<其中n表示序列中元素个数，i表示当前已处理过的（想象上）元素个数。
这个算法实现上比较优雅（显然指的不是工程上的设计优雅），但是在使用上可能会有一个小问题：前面提到输入元素都是唯一不同的。那么如果输入中包含重复元素，这个算法将会生成重复的结果。
虽然在数学上倾向于确保全排列元素的互异性，但是在实际应用中，这点还是很难避免。
一种比较直接的方法是递归前确保下一次产生的元素不会发生重复。具体策略是：
在交换A[i],A[j]前，保证A[i..j-1]里没有元素和A[j]相等。
这么做是基于两个原因：
(1)每次交换A[i],A[j]后产生排列，只需要确保P(A[i],..,P[j])的排列不重复即可
(2)如果在交换A[i],A[j]前，A[i..j-1]里有元素和A[j]相等，即存在 A[k] = A[j], i<=k
void GenePermu(int A[], int i, int n)
{
if (i == n-1)
{
for (int k = 0;
k < n;
++k)
{
coutbasing on next_permutation
【全排列算法（不含重复元素，包含重复元素，字母序排列）】 另一种常用的算法则是对输入的一个排列构造下一个字典序的排列。有关字典序请参考http://en.wikipedia.org/wiki/Lexicographical_order
比如，对于输入的1,3,2，会输出下一个字典序排列2,1,3
算法的大致思路如下：
(1)对于输入的字典许排列，反向查找第一对满足a[j] (2)仍旧反向查找一个下标k，使得 a[j] (3)交换a[j]和a[k]
(4)使得a[i+1..n]按递增排列
说完思路，重点是分析。
第一步是根据字典序定义进行的。
而在找到满足条件的j后，有一个隐藏的性质，即：a[j+1..n]是（非严格）单调递减排列的，这点可以由反证法结合第一步导出矛盾来证明。所以第二部中只需要查找第一个满足条件的k，也满足了最小值原则。
在第四步中，由于上面逆序条件可知，递增排列性质只需要逆置a[j+1..n]即可。
接下来考虑两个意外情况：(1)元素重复 (2)输入已经是最后一个字典序排列
其实第一个问题已经得到了解决，因为第一步中我们要满足的条件是严格的小于。并且因为这个断言，我们在第二步中查找满足条件的k时，是一定可以找到这样的k的
第二个问题比较隐蔽，如果输入已经是最后一个字典序，亦即是一个单调递减排列，那么第一步会直接越界。解决方法只需要简单保证j非负即可。
另外，如果要用这个算法产生全排列，那么则应该保证输入排列是第一个字典序，亦即单调递增排列。
代码的一个实现如下：
bool GetNextPermu(int A[], int n)
{
int j = n - 2;
while (A[j] >= A[j+1] && j >= 0)
{
--j;
} if (j < 0)
{
wcout<= A[i])
{
--i;
} swap(A[j], A[i]);
int l = j + 1, r = n - 1;
while (l < r)
{
swap(A[l], A[r]);
++l;
--r;
} return true;
} 推荐阅读
- 危险也是机会
- 画解算法（1.|画解算法：1. 两数之和）
- 活着就是生命的全部意义
- Guava|Guava RateLimiter与限流算法
- 一个健康的APP和健全的人格大体类似
- NeuVector 会是下一个爆款云原生安全神器吗（）
- 全过程工程咨询——时间管理（12）
- 别墅庭院设计，不同的别墅庭院设计也给人视觉上完全不一样的！
- 一个选择排序算法
- 不让记忆、感觉、情绪成为孩子的负累|不让记忆、感觉、情绪成为孩子的负累|《全脑教养法》（四）