Description
题目描述： 大家知道，给出正整数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六个排列。 任务描述： 给出某个排列，求出这个排列的下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 10Sample Output
3 1 2 1 2 3 1 2 3 4 5 6 7 9 8 10 搜STL相关题目的时候搜到的， http://blog.csdn.net/xieshimao/archive/2011/01/03/6114307.aspx #include<stdio.h> #include<algorithm> using namespace std; int a[1200]; int main(){ int t,n,k; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&k); for(int i=0; i<n; i++) scanf("%d",&a[i]); for(int i=0; i<k; i++) next_permutation(a,a+n); for(int i=0; i<n-1; i++) printf("%d ",a[i]); printf("%d/n",a[n-1]); } return 0; } 查了一下next_permutation的相关知识： 下面转自http://blog.csdn.net/aipb2008/archive/2008/03/29/2227490.aspx “在标准库算法中,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 );
两个重载函数,第二个带谓词参数_Comp,其中只带两个参数的版本,默认谓词函数为"小于".
返回值:bool类型
分析next_permutation函数执行过程:
假设数列 d1,d2,d3,d4……
范围由[first,last)标记，调用next_permutation使数列逐次增大，这个递增过程按照字典序。例如，在字母表中，abcd的下一单词排列为abdc，但是，有一关键点，如何确定这个下一排列为字典序中的next，而不是next->next->next……
若当前调用排列到达最大字典序，比如dcba，就返回false，同时重新设置该排列为最小字典序。
返回为true表示生成下一排列成功。下面着重分析此过程：
根据标记从后往前比较相邻两数据，若前者小于（默认为小于）后者，标志前者为X1（位置PX）表示将被替换，再次重后往前搜索第一个不小于X1的数据，标记为X2。交换X1，X2，然后把[PX+1，last)标记范围置逆。完成。
要点：为什么这样就可以保证得到的为最小递增。
从位置first开始原数列与新数列不同的数据位置是PX，并且新数据为X2。[PX+1，last)总是递减的，[first,PX)没有改变，因为X2>X1,所以不管X2后面怎样排列都比原数列大，反转[PX+1，last）使此子数列(递增)为最小。从而保证的新数列为原数列的字典序排列next。
明白了这个原理后，看下面例子：
int main(){ int a[] = {3,1,2};do{ cout << a[0] << " " << a[1] << " " << a[2] << endl;} while (next_permutation(a,a+3)); return 0;}
输出：312/321 因为原数列不是从最小字典排列开始。
所以要想得到所有全排列
int a[] = {3,1,2}; change to int a[] = {1,2,3};
另外，库中另一函数prev_permutation与next_permutation相反，由原排列得到字典序中上一次最近排列。
所以
int main(){ int a[] = {3,2,1};do{ cout << a[0] << " " << a[1] << " " << a[2] << endl;} while (prev_permutation(a,a+3)); return 0;}
才能得到123的所有排列。
”
