C++STL库神器：next_permutation与prev_permutation

阳光穿透心脏的1/2处 2023-02-27 13:52 127阅读 0赞

##### next\_permutation() 与 prev\_permutation() #####

**相同之处**  
头文件：algorithm  
使用方法：  
next\_permutation(s.begin(), s.end());  
将s字符串 s 转换为下一个全排列。  
next\_permutation(arr, arr+n);  
将数组 arr 转换为下一个全排列。  
prev\_permutation(s.begin(), s.end());  
将s字符串 s 转换为上一个全排列。  
prev\_permutation(arr, arr+n);  
将数组 arr 转换为上一个全排列。

**不同之处**  
排序方式相反：  
next\_permutation() 是按照字典升序的方式生成的排列。  
prev\_permutation() 是按照字典降序的方式生成的排列。

--------------------

##### 什么是字典升序、降序？ #####

大家知道，给出正整数n，则1到n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，列出1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1六个排列。 这就是字典升序排列，字典降序排列则与字典升序排列相反。

--------------------

##### 例题 #####

[测试平台][Link 1]  
给出某个排列，求出这个排列的下k个排列，如果遇到最后一个排列，则下1排列为第1个排列，即排列1 2 3…n。  
比如：n = 3，k=2 给出排列2 3 1，则它的下1个排列为3 1 2，下2个排列为3 2 1，因此答案为3 2 1。

Input  
第一行是一个正整数m，表示测试数据的个数，下面是m组测试数据，每组测试数据第一行是2个正整数n( 1 <= n < 1024 )和k(1<=k<=64)，第二行有n个正整数，是1，2 … n的一个排列。

Output  
对于每组输入数据，输出一行，n个数，中间用空格隔开，表示输入排列的下k个排列。  
Sample Input

3  
3 1  
2 3 1  
3 1  
3 2 1  
10 2  
1 2 3 4 5 6 7 8 9 10  
Sample Output

3 1 2  
1 2 3  
1 2 3 4 5 6 7 9 8 10

--------------------

每调用一次 next\_permutation(arr, arr+n) ，arr 生成下一个全排列数组，题目要求下k个，那么则调用 k 次 next\_permutation(arr, arr+n) 即可得到结果。

值得注意的是：  
当 next\_permutation() 返回 false 时，表明回到了全排列中第一个排列（最小排列），恰好符合题意。**如果遇到最后一个排列，则下1排列为第1个排列，即排列1 2 3…n**。

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    int arr[1050];
    
    int main(){ 
    	int T;
    // freopen("data.txt", "r", stdin);
    	scanf("%d", &T);
    	for(int i=0; i<T; i++){ 
    		int n, k;
    		scanf("%d%d", &n, &k);
    		for(int j=0; j<n; j++)
    			scanf("%d", &arr[j]);
    		
    		while(k--)
    			next_permutation(arr, arr+n);
    
    		for(int j=0; j<n-1; j++)
    			printf("%d ", arr[j]);
    		
    		printf("%d\n", arr[n-1]);
    	}
    	
    	return 0;
    }

如果文章对你有帮助的话，请给我个赞吧：)

[Link 1]: http://poj.org/problem?id=1833