Permutation Generation
Permutation Generation
Problem-A题目描述样例输入Asdescribed inWs14.11,fora setofn items(a1,a2a3...an)therearen!permutations!Your job is toCalculateALLPermutationsofa set consiting Integers from143ton(n<=9)byRECURSION.1224输入Thefirstlineconsistoftwointeger:n(n<=9).m<=100;样例输出EachofthefollowingmlinesconsistsonesingleIntegerx(1<=x<=n!)输出[1,2,3,4][1,2,4,3]Foreachx.outputa lineconsistingofthex-thpermutation(assummingthat[4,3,2,1]all permutations are sorted lexicographicallyinthefollowingformat:(a'1.a'2...a'n)
Problem-A
How to solve it?· Basic ideas?i-thpermutationQueryPermutationi-th?Generator
How to solve it? • Basic ideas? Permutation Generator Query i-th? i-th permutation
#include<aigorithms#include<cstdio>方法-1:int n,a[1001];int FindO(for(int i-n-1; i; i--)if(a[i]<a[i+il)returni:循环n！次：return O;每次T找到最后一个k满足a[k]<a[k+1]int main()(找到k后面最小的的a[t]满足a[t]>a[k]scanf("%d"，&n);交换a[k]和a[t]for(int i=l; i<=n; i++) a[i]=i;反转a[k+1]到a[n]while(1)(1for(inti=i;i<-n;i++)printf("%da[i);printf("ln")int k-Find(),t=O;if(Ik)break;为什么能够生成所有permutation？for(int i=k+1; i<=n; i++)if(a[i]>a[k]&&(ltlla[i]<a[t]))t=i;是否按照字典序？std::swap(a[k],a[t]);std::reverse(a+k+1, a+n+1);子子
方法-1： 循环n！次: 每次{ 找到最后一个k 满足a[k]<a[k+1] 找到k 后面最小的的a[t] 满足a[t]>a[k] 交换a[k] 和a[t] 反转a[k+1] 到a[n] } 为什么能够生成所有permutation？ 是否按照字典序？
#include<algorithm>方法-2#include <cstdio)intn,a[1001];void Dfs(int st){if(st==n)(for(int i=1;i<=n;i++)printf("%d",a[ij);为什么能够生成所有permutation？printf("n");return;子是否按照字典序？for(int i=st;i<=n;i++)(std::swap(a[i],a[st]);Dfs(st+1);怎么修改才能使得按照字典序？std::swap(a[i],a[st]);J3DFS(0):int main((生成数组a中从第i个元素到第n个元素所能构成scanf("%d"，&n);的所有Permutationfor(int i-1; i<=n; i++) a[i] =(i;Dfs(1);3
方法-2 为什么能够生成所有permutation？ 是否按照字典序？ 怎么修改才能使得按照字典序？ DFS(i): 生成数组a中从第i个元素到第n个元素所能构成 的所有Permutation