Problem F
Name That Permutation
The concept of permutations comes up frequently in the analysis of computer algorithms, in probability theory, and in many other fields. For many algorithmic problems, the easiest brute-force-type solution is to enumerate all possible permutations of some list or set, and test each permutation to see if it provides the correct solution. One problems which is easy to view this way is the classic traveling salesman problem. This is not to suggest that enumerating all permutations is the most efficient solution method!
For this problem, write a program that takes a list of unique numbers from $1$ to $n$ and produces the $k$th permutation of that list. The first permutation ($k=0$) is the list in sorted order, i.e. $1, 2, 3, \ldots , n$. The last permutation ($k=n!-1$) is the list in reverse sorted order. The progression of permutations follows the standard numeric sorting rules. So for $n=4$, the following are the order of permutations, from $k=0$ to $k=4!-1=23$:
|
$k$ |
permutation |
$k$ |
permutation |
$k$ |
permutation |
$k$ |
permutation |
|
$0$ |
$1~ 2~ 3~ 4$ |
$6$ |
$2~ 1~ 3~ 4$ |
$12$ |
$3~ 1~ 2~ 4$ |
$18$ |
$4~ 1~ 2~ 3$ |
|
$1$ |
$1~ 2~ 4~ 3$ |
$7$ |
$2~ 1~ 4~ 3$ |
$13$ |
$3~ 1~ 4~ 2$ |
$19$ |
$4~ 1~ 3~ 2$ |
|
$2$ |
$1~ 3~ 2~ 4$ |
$8$ |
$2~ 3~ 1~ 4$ |
$14$ |
$3~ 2~ 1~ 4$ |
$20$ |
$4~ 2~ 1~ 3$ |
|
$3$ |
$1~ 3~ 4~ 2$ |
$9$ |
$2~ 3~ 4~ 1$ |
$15$ |
$3~ 2~ 4~ 1$ |
$21$ |
$4~ 2~ 3~ 1$ |
|
$4$ |
$1~ 4~ 2~ 3$ |
$10$ |
$2~ 4~ 1~ 3$ |
$16$ |
$3~ 4~ 1~ 2$ |
$22$ |
$4~ 3~ 1~ 2$ |
|
$5$ |
$1~ 4~ 3~ 2$ |
$11$ |
$2~ 4~ 3~ 1$ |
$17$ |
$3~ 4~ 2~ 1$ |
$23$ |
$4~ 3~ 2~ 1$ |
Input
Input consists of up to $1\, 000$ test cases, one per line. Each test case has two integers $1 \leq n \leq 50$ and $0 \leq k \leq n!-1$. Input ends at the end of file.
Output
For each test case, print a line containing the $k$th permutation of the numbers $1$ through $n$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 10 3 |
3 1 2 1 2 3 4 5 6 7 9 10 8 |
