Bank Permutation Codes
Autumn Tournament (2008)
Submission name: banka.cpp
Problem summary
A bank code is a permutation of 1..K. Print every code whose 1-based lexicographic rank lies between N and M, inclusive. Numbers in a code are compared as integers and printed separated by spaces.
Input
K, then N M.
Output
One permutation per line, in increasing lexicographic order.
Constraints
2<K<13; 0<N<M<400000000; M−N≤1000000. Requested ranks must refer to existing permutations.
Worked example
Original statement sample.
Input
3 2 4
Output
1 3 2 2 1 3 2 3 1
Solution analysis
- Do not generate all permutations before rank N: N may be hundreds of millions. Convert N−1 to factorial-block choices. With r unused numbers remaining, each possible first choice starts a block containing (r−1)! permutations.
- Choose index rank/(r−1)! from the sorted unused numbers, remove it, then replace rank by rank%(r−1)!. Repeating constructs the first required permutation directly. Use next_permutation for each subsequent rank through M.
- For K=3 and N=2, zero-based rank is 1. Its first choice is index 1/2!=0, so take 1; the residual rank 1 chooses the second remaining number 3, then 2. Thus the interval begins 1 3 2 and continues 2 1 3, 2 3 1.
Why it works
At each position lexicographic order partitions the remaining permutations into equal factorial-size blocks. Division selects exactly the block containing the requested rank and remainder selects its rank inside that block. This proves unranking by induction. next_permutation then enumerates exactly the following ranks in order.
Watch out. Ranks in the input are 1-based. Use 64-bit factorials and ranks. Print spaces between numbers, especially for 10,11,12. The source does not explicitly state M≤K!, but a requested code must exist.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int size;
long long firstRank,lastRank;
cin>>size>>firstRank>>lastRank;
vector<long long>factorial(size+1,1);
for(int i=1;i<=size;i++){
factorial[i]=factorial[i-1]*i;
}
vector<int>unused(size);
iota(unused.begin(),unused.end(),1);
vector<int>permutation;
long long rank=firstRank-1;
for(int remaining=size;remaining>0;remaining--){
// Every possible next number owns (remaining-1)! consecutive ranks.
int index=static_cast<int>(rank/factorial[remaining-1]);
if(index>=static_cast<int>(unused.size())){
return 0;
}
permutation.push_back(unused[index]);
unused.erase(unused.begin()+index);
rank%=factorial[remaining-1];
}
for(long long current=firstRank;current<=lastRank;current++){
for(int i=0;i<size;i++){
if(i>0){
cout<<' ';
}
cout<<permutation[i];
}
cout<<'\n';
if(current!=lastRank&&!next_permutation(permutation.begin(),permutation.end())){
break;
}
}
}