题目
Permutation
Accept:217 Submit:706
Time Limit:1000MS Memory Limit:65536KB
Description
We all know that , when there are n positive integers (namely 1…n) , we can use these n integers to construct n! kinds of permutations . Sort these permutations in lexicographic order . For example , when n = 3 , we can permute 1 2 3,1 3 2,2 1 3, 2 3 1, 3 1 2 , 3 2 1 these 6 kinds of permutations.
Now , we want to know , with the given permutation , calculate the next k permutation . If the permutation is the last permutation in order , its next permutation is the first permutation , namely 1 2 3 … n.
e.g. when n = 3 , k = 2 , giving the permutation 2 3 1 , thus its next 1 permutation is 3 1 2 , its next 2 permutation is 3 2 1 , so the answer is 3 2 1 .
Input
The first line is a positive integer m , indicating the number of test cases . Then m test cases . In every test case , the first line is 2 positive integers n (1 <= n < 1024) and k (1 <= k <= 64) ; the second line are n positive integers , which is one of the “ 1 2 3 … n” s’ permutation.
Output
For each test case , print one line , n numbers , with spaces separating every number , indicating the given permutation ‘s next k permutation.
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
/*************************************************************************
> File Name: next_permutation.c
> Author: narutolby
> Mail:willianlby@yahoo.cn
> Created Time: 2013年01月08日 星期二 09时26分34秒
************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
int num[1024];
typedef struct test1{
int len;
int nextP;
int num[1024];
}Test;
void printfArray(int num[],int len){
int i=0;
for(;i<=len;i++){
printf("%d",num[i]);
if(i<len){
printf(" ");
}
}
printf("\n");
}
void swap(int num[],int i,int j){
int t=0;
t=num[i];
num[i]=num[j];
num[j]= t;
}
void reverse(int num[],int start,int end){
for(;start<end;start++,end--){
swap(num,start,end);
}
}
void next_permutation(int num[],int len,int k){
int j=len;
int loop = 0;
while(j>0){
if(num[j]>num[j-1]){
int minMax = num[j],n=j+1,minMaxIndex=j;
for(;n<=len;n++){
if(num[n]<minMax && num[n]>num[j-1]){
minMax = num[n];
minMaxIndex = n;
}
}
swap(num,j-1,minMaxIndex);
int f=j,g=len;
reverse(num,f,g);
loop++;
if(loop==k){
printfArray(num,len);
break;
}
j=len;
}else{
j--;
}
}
if(loop<k){
reverse(num,0,len);
loop++;
if(loop==k){
printfArray(num,len);
}else{
next_permutation(num,len,k-loop);
}
}
}
int main(){
int times,time=0;
scanf("%d",×);
Test *testArray[times] ;
// printf("times:%d\n",times);
for(;time<times;time++){
// printf("current time:%d\n",time);
Test *test = (Test*)malloc(sizeof(Test));
scanf("%d %d",&test->len,&test->nextP);
// printf("%d %d\n",test->len,test->nextP);
int m =0;
for(;m<test->len;m++){
scanf("%d",&test->num[m]) ;
// printf("%d ",test->num[m]);
}
// printf("\n");
testArray[time] = test;
}
// printf("end\n");
time=0;
for(;time<times;time++){
Test *t1 = testArray[time];
next_permutation(t1->num,t1->len-1,t1->nextP);
free(t1);
}
return 0;
}
解题思路
本题的输入为int型数组array和int型k值,以当前数组开始,求第k个按字典顺序的全排列输出。
解题步骤
所谓字典顺序,就是数组之间会从索引0开始,依次比较,如果相同,则比较下一个元素,直到遇到不同大小的元素为止,大元素所在的数组字典顺序在小元素所在数组的后面,依次类推。
回到本题,如输入数组1,2,3,4,5为按照字典顺序的第一个,5,4,3,2,1为按照字典顺序的最后一个,也就是数字越大的数字所在的位置越靠前,所在的字典顺序越靠后。
按照这个思路,所以我们的解题步骤如下:
(1)从后向前遍历数组,记录第一个当前元素大于前一个元素的位置,记录为i;
(2)从第i个元素开始,向后搜索大于i-1最小的元素,记录为j,交换i和j的元素值,并将从第i个元素开始以后的元素倒置。
经过以上两个步骤就求出了当前数组在字典顺序下的下一个全排列。
同理,可求出第k个。
分享到:
相关推荐
实验室安全试题&答案 北邮 题目有重复的
BUPT信号与系统2006真题,为您北京邮电大学考研之路奠定一滴基础。
BUPT信安数字内容安全期末试题
BUPT计算机学院大一新生入学课程 - 计算导论与程序设计,该包内的OJ题可供参考,整合了源代码和可执行文件。历届上机题不一定完全一样,但还是有参考价值的。
这里我汇总了绝大部分北邮BUPT OJ 上的中文题,中文题也就都是往年题。有从10年开始到14年的所有机试往年题。我的博客里有上述文档里所有的题。谁知道怎么降低下载积分?现在看不到这个选项了
2010-2011软工期中试题_有答案(BUpt)
计组实验bupt .rar
2023bupt大创遥感语义分割.rar2023bupt大创遥感语义分割.rar2023bupt大创遥感语义分割.rar2023bupt大创遥感语义分割.rar2023bupt大创遥感语义分割.rar2023bupt大创遥感语义分割.rar2023bupt大创遥感语义分割.rar2023...
BUPT计算机学院大三上数据库系统原理配套实验。压缩包中包含实验一-实验六,包含数据库实验报告及数据,最终数据库课程成绩93
工数是我唯一一门挂掉的科目,大家一定要好好刷题啊! 补考和正式考试同等难度,请不要掉以轻心! 本合集包括: 2013——2014 学年第二学期 《工程数学》期末...2020——2021 学年第一学期《工程数学》考试试题(补考)
期中卷子,期末卷子,课本答案,作业,ppt,学习笔记,当时的全套学习记录
bupt的java作业大全 HelloWorld EightQueen八皇后 展示多态应用例子 作业报告,word中有源代码
疫情在家学习,必备打铃器,BUPT原汁原味上下课音乐,带你梦回学校
BUPT计算机系统csapp四次实验报告
BUPT计算机学院大雾,期末试卷,ppt
第二章-第七章 图数据库 文档数据库 列祖数据库作业
BUPT大三蒋老师linux环境课程,包含4次实验参考以及相关课件,Mooc上有相关课程,期末成绩95
分布式温控系统的代码以及可执行文件。采用python语言进行编程,利用pyqt5进行图形化设计,采用mysql数据库进行存储。期末98
BUPT 自动机实验,NFA转化DFA,java代码加实验报告
用VHDL写的计时器,数字电路与逻辑设计实验 原创