题面描述

给定参数$n$，从$1$到$n$会有$n$个整数:$1, 2, 3......n$。这$n$个数字共有$n!$种排列。我们需要按大小顺序升序列出所有排列的情况，并一一标记。给定$n$和$k$，返回第$k$个排列。

解题思路

1. 排列生成的性质：
   • 任何$n$的排列都可以通过固定某个数字，剩余的数字再进行全排列来生成。
   • 比如，对于$n = 3$，固定数字$1$，则其余$2$的排列为$2,3$。

题目内容

给定参数 $n$，从 $1$ 到 $n$ 会有 $n$ 个整数：$1,2,3,…,n$, 这 $n$ 个数字共有 $n!$ 种排列。

按大小顺序升序列出所有排列的情况，并一一标记，当 n = 3 时,所有排列如下:

• “123”
• “132”
• “213”
• “231”
• “312”
• “321”

给定 $n$ 和 $k$，返回第 $k$ 个排列。

输入描述

输入两行，第一行为 $n$，第二行为 $k$，

给定 $n$ 的范围是$[1, 9]$, 给定 $k$ 的范围是$[1, n!]$。

输出描述

输出排在第 $k$ 位置的数字。

样例1

输入

3
3

输出

213

说明

$3$的排列有$123,132,213,…$，那么第三位置就是$213$

样例2

输入

2
2

输出

21

说明

$2$的排列有$12,21$，那么第二位置的为$21$。