赞
踩
计算序列全排列的函数:next_permutation(start,end),和prev_permutation(start,end)。这两个函数作用是一样的,区别就在于前者求的是当前排列的下一个排列,后一个求的是当前排列的上一个排列。都包含在头文件 #include<algorithm> 里面。
假设我们想 求 1 到 n 的全排列代码如下:
- #include <stdio.h>
- #include <algorithm>
- using namespace std;
- int main(){
- int n;
- while(scanf("%d",&n)&&n){
- int a[1000];
- for(int i=0;i<n;i++){
- scanf("%d",&a[i]);
- }
- sort(a,a+n);
- do{
- for(int i=0;i<n;i++)
- printf("%d ",a[i]);
- printf("\n");
- }while(next_permutation(a,a+n));
- }
- return 0;
- }
我们看下测试样例:
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int main()
- {
- int num[3]={1,2,3};
- do
- {
- cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
- }while(next_permutation(num,num+3));
- return 0;
- }
测试结果如下:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
但是如果我们将序列变一下的话,不是按照递增序列排的话,那么输出就会少很多,比如:
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int main()
- {
- int num[3]={2,1,3};
- do
- {
- cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;
- }while(next_permutation(num,num+3));
- return 0;
- }
测试结果如下:
2 1 3
2 3 1
3 1 2
3 2 1
同样,prev_permutation(start,end)函数是和next_permutation(start,end)用法相同。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。