C++中next_permutation函数的使用方法、原理及手动实现

一、next_permutation的使用方法

1、头文件

naxt_permutation函数包含在algorithm库中

2、参数

和sort的参数一样，一般传两个参数，第一个是排列开始的地址，第二个是排列结束的下一个地址，如实现数组第1-3排列的下一个排列：next_permutation(a,a+3)。一般作用对象是数组。

3、作用

next_permutation是求当前排列的下一个排列（按字典序升序的下一个序列），如1234的next_permutation是1243。在全排列当中经常会用。

4、返回值

返回值是Ture或者False，若当前排列有下一个排列，则返回Ture，反之返回False：如54321的返回值为False。该函数会直接修改数组为下一个排列。

二、原理

实现原理就是①从后往前找原数组中第一个a[i] < a[i+1]的地方，其后面全是降序，说明已经排好了，所以我们就要将a[i]的值改大一点。②将a[i]和其后面所有数中大于他的最小的数交换位置，则a[i]后面的数仍是个降序。③然后将其后面这些降序的元素翻转，就得到了原排列的下一个增序排列了。
例如：对于排列2431来说，①我们先找到2和4处，然后交换2和3的位置，就得到了3421；然后翻转421，就得到了3124，则3124就是2431的下一个排列，如下图。

三、手动实现

模拟上述原理即可
代码：

int k = n;
while(a[k-1] > a[k])
	k--;	//①
int t = k;
while(a[t+1] > a[k-1])
	t++;
swap(a[k-1],a[t]);	//②
reverse(a+k,a+n+1);	//③