poj1741，poj1833 排列

2023-10-18 阅读 28 评论 0

摘要：排列 Time Limit:?1000MS?Memory Limit:?30000KTotal Submissions:?20842?Accepted:?7953 Description 題目描述：?大家知道，給出正整數n，則1到n這n個數可以構成n！種排列，把這些排列按照從小到大的順序（字典順序）列出，

排列

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。?

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 }