首页 > 代码库 > 白话 STL next_permutation 原理
白话 STL next_permutation 原理
翻译自stackoverflow 英语好的同学可以自己去看一下。
什么是next permutation
下面是四个元素{1,2,3,4}的排列
1 2 3 41 2 4 31 3 2 41 3 4 21 4 2 31 4 3 22 1 3 4...
每一行都是一个排列。
我们如何从一个排列转到下一个排列呢？我们可以将如上4个数的排列当做一个数。每一个数的下一个排列就是发现下一个比它大的数。
next_permutation就是寻找这些元素所组成的数字的升序排列中的下一个数。
比较绕口，可以看个例子
1 4 2 3 = 1423
1 4 3 2 = 14322 1 3 4 = 2134 ....
1 4 3 2 的next_permutation就是 升序排列中下一个比它大的数2134
如何寻找next_permutation
还是用1432位例子，现在它是用{1,2,3,4}所能组成的以1开头的最大的四位数。我们想要找到排序中下一个比它大的数该如何呢？
就是用下一个比1大的元素替代1（就是2），然后加上剩下的三个元素的所能排出的最小数值（也就是134）
这样就发下了1432的next_permutation 2134
过程如下：
1.寻找到1的右边第一个比1大的元素
1 4 3 2 ----> 2 4 3 1 （注意：这时候的右边三个元素是递减的，我们要求右边三个元素所能排成的最小数值时，只需要将431逆序就可以了）
2.求出右边元素所能组成的最小排列
2 4 3 1 ---->2 1 3 4 <---next_permutation of 1 4 3 2
如何判断一个数应该加入到排列中呢
那么，我们怎么知道1432是1开头的最大的数呢？观察可以发现，当1的右边也就是432是递减的时候！
也就是，在一个元素的最右边的元素所排成的序列是递减的时候！
阅读源码
next_permutation的源码见下面，这里只摘录最重要的部分
while (true) { It j = i; i--; if (*i < *j) { //something.. } if (i == begin) { //something }}
因为i的初值是end，j是i的后一个元素。那么这个while循环可以解释为
while (true){ 1如果i的右边是降序，那么做一些事情，返回 2如果i是开头，那么这就是最后一个排列，做一些事，返回。 继续循环，递减i j 最后总会符合上面条件中的一个}
首先解释2,如果i已经是开头了，那么表示这个排列已经完全是递减的（也就是 4,3,2,1）那么我们将整个数组逆序（得到（1,2,3,4），得到排列的初值。
现在解释1,如果i的右边已经都是降序了，这时候*i < *j （比如i=0,j=1 (1,4,3,2)) 。i代表右边都是降序的最小的下标值。
这时候，我们需要做的就是从右边，找到第一个大于i的值，然后将他和i交换，然后再将右边的整体逆序。
代码如下：
It k = end;while (!(*i < *--k)) /* pass */;iter_swap(i, k);reverse(j, end);return true;
附：next_permutation代码
#include <vector>#include <iostream>#include <algorithm>using namespace std;template<typename It>bool next_permutation(It begin, It end){ if (begin == end) return false; It i = begin; ++i; if (i == end) return false; i = end; --i; while (true) { It j = i; --i; if (*i < *j) { It k = end; while (!(*i < *--k)) /* pass */; iter_swap(i, k); reverse(j, end); return true; } if (i == begin) { reverse(begin, end); return false; } }}int main(){ vector<int> v = { 1, 2, 3, 4 }; do { for (int i = 0; i < 4; i++) { cout << v[i] << " "; } cout << endl; } while (::next_permutation(v.begin(), v.end()));}