本题主要是STL库里的next_permutation的用法!

在标准库算法中,next_permutation应用在数列操作上比较广泛.这个函数可以计算一组数据的全排列.但是怎么用,原理如何。
首先查看stl中相关信息.
函数原型:

template<class BidirectionalIterator>
   bool next_permutation(
      BidirectionalIterator _First,
      BidirectionalIterator _Last
   );
template<class BidirectionalIterator, class BinaryPredicate>
   bool next_permutation(
      BidirectionalIterator _First,
      BidirectionalIterator _Last,
      BinaryPredicate _Comp
   );
简单举例
int a[] = {3,1,2};
do{
     cout << a[0] << " " << a[1] << " " << a[2] << endl;
}
while (next_permutation(a,a+3));
return 0;
}

输出:312
            321
范围由[first,last)标记,调用next_permutation使数列逐次增大,这个递增过程按照字典序。当存在比前一个序列大的序列时就返回true,否者返回false(a为321时next_permutation(a,a+3)返回false,且a变为123)。
本题代码
#include<iostream>
#include<algorithm>
using namespace std;
int a[1003];
int main(){
     int n,m,i;
  while(cin>>n>>m){
   int count=1;
   for(i=1;i<=n;i++)
    a[i]=i;
   while(next_permutation(&a[1],&a[n+1])){
    count++;
    if(count==m) break;
   }
         for(i=1;i<n;i++) printf("%d ",a[i]);
         printf("%d\n",a[n]);
  }
  return 0;
}
有兴趣的还可以去了解其内部实现,和pre_permutation的用法。

发表评论

电子邮件地址不会被公开。

Post Navigation