本文共 1793 字，大约阅读时间需要 5 分钟。
1. 数组的全排列
由题入坑求给定数组的全排列。如：输入： 1，2，3输出： 1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2
这里来一道算法题：
算法题：实现一个整型数组的全排列，void perm(int list[], int k, int m)参数说明：list，数组；k开始位置，m个数。
用递归算法实现代码如下：void perm(int list[], int k, int m){ if ( k==m ) { copy(list,list+m,ostream_iterator (cout," ")); cout< 明白什么是全排列后，再来看看next permutation这道题，递归的方法是较简单并且容易想到的，我们尝试非递归的解法。关于原理部分，基本上都是摘抄自《STL源码剖析》。
- 《STL源码剖析》： 在当前序列中，从尾端往前寻找两个相邻元素，前一个记为*i，后一个记为*ii，并且满足*i < *ii。然后再从尾端寻找另一个元素*j，如果满足*i < *j，即将第i个元素与第j个元素对调，并将第ii个元素之后（包括ii）的所有元素颠倒排序，即求出下一个序列了。看具体例子，一个排列为 124653，如何找到它的下一个排列。
第一步：找最后面1个数字的下一个全排列。
124653， 显然最后1个数字3不具有下一个全排列。
第二步：找最后面2个数字的下一个全排列。
1246 53, 显然最后2个数字53不具有下一个全排列。第三步：找最后面3个数字的下一个全排列。
124653，显然最后3个数字 653 不具有下一个全排列。 插曲：到这里相信大家已经看出来，如果一个序列是递减的，那么它不具有下一个排列第四步：找最后面4个数字的下一个全排列。
12 4653, 我们发现显然最后4个数字，4563 具有下一个全排列。因为它不是递减的，例如6453， 5643总结上面的操作，并总结出重复上面操作的两种终止情况：
1：从后向前比较相邻的两个元素，直到前一个元素小于后一个元素，停止 2：如果已经没有了前一个元素，则说明这个排列是递减的，所以这个排列是没有下一个排列的。我们找到了 这个 "i"，接下来要从尾端寻找 j （*i < *j）
12 4653， 从后向前找第一个比 “4”大的， 找到 “5”，将 这两个元素进行交换。得到： 12 5643
将第 ii 个元素之后（包括ii）的所有元素颠倒排序。此时 ii 指向的是 6
所以： 643 颠倒为： 346
so， 124653 的下一个序列为： 125346
void nextpermutation(vector & num){ if (num.size() <= 1) return; int i = (int)num.size() - 1; while (i > 0 && num[i] <= num[i-1]) --i; if (i == 0) { //整个数组是倒叙排列的 reverse(num.begin(), num.end()); return; } --i; int j = (int)num.size() - 1; while (num[i] >= num[j]) --j; swap(num[i], num[j]); reverse(num.begin() + i + 1, num.end());}int main(){ vector vec = { 1, 2, 4, 6, 5, 3 }; nextpermutation(vec); for (auto &i:vec) cout << i << " ";; system("pause"); return 0;} 参考文献：
转载地址：http://bokmi.baihongyu.com/