排列
Time Limit:?1000MS | ? | Memory Limit:?30000K |
Total Submissions:?20842 | ? | Accepted:?7953 |
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。?
大家知道,給出正整數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 10
Sample Output
3 1 2 1 2 3 1 2 3 4 5 6 7 9 8 10
Source
qinlu@POJ
1 #include <iostream> 2 #include <string> 3 #include <algorithm> 4 #include <string.h> 5 #include <cstring> 6 #include <math.h> 7 #include <stdio.h> 8 9 #define mem(a) memset(a,0,sizeof(a)) 10 #define maxn 1025 11 using namespace std; 12 int a[maxn]; 13 int main(){ 14 ios::sync_with_stdio(0); 15 int m,n,k; 16 scanf("%d",&m); 17 while(m--){ 18 scanf("%d%d",&n,&k); 19 int j=0; 20 mem(a); 21 for(int i=0;i<n;++i){ 22 scanf("%d",&a[i]); 23 } 24 while(k--){ 25 next_permutation(a,a+n); 26 } 27 for(int i=0;i<n;i++){ 28 if(i!=0) 29 printf(" "); 30 printf("%d",a[i]); 31 } 32 printf("\n"); 33 } 34 return 0; 35 }
?