数列→順列の辞書順で何番目か
Editorial - AtCoder Beginner Contest 276の方法です．数列$S = (S[0], S[1], ..., S[N])$が順列の辞書順で何番目かを返す関数をつくる．
これは，
「数列$(S[0], S[1], ..., S[N])$より辞書順で小さいか等しい数列の数」
＝「先頭が$S[0]$でない場合の↑の数」＋「先頭が$S[0]$の場合の↑の数」
＝「（先頭として選べる$S[0]$未満の数の個数）×（それ以外の数を任意の順番で並べる方法の数）」＋「（$S[0]$を除いた数列$(S[1], ..., S[N])$より辞書順で小さいか等しい数列の数」
2項目は1つ要素数の少ない問題になったので，同じことを繰り返せば良い．
# fa[x] = x! (階乗) fa = [1] * (N + 1) for i in range(N): fa[i + 1] = fa[i] * (i + 1) def sequence_to_order(S): res = 0 while S: res += sum(s < S[0] for s in S) * fa[len(S) - 1] S = S[1:] return res
順列の辞書順で何番目か→数列
Editorial - AtCoder Beginner Contest 276の方法です．辞書順で$k$番目の数列を求める関数をつくる．
$i$項目を$S[i]$に決めると，$i + 1$項目以降の選び方は$(N - i) !$通りある．したがって，$S[i]$が選べる数の中で$j$番目の大きさだとすると，$(S[i],...)$の数列の前には辞書順で$(N - i) ! \times (j - 1)$個の数列があることになる．
よって，各ステップで
- $S[i]$を「$(S[i],...)$の数列の前に$k$を超えないギリギリの個数の数列があるように選び
- $k$から↑の「ギリギリの個数」を減じて
- $S[i]$を除いた残りの数からなる集合で同じ問題を解く
上では1-indexedで考えたが，実装では0-indexedであることに注意（0番目に大きい数列が辞書順で最小）．
# fa[x] = x! (階乗) fa = [1] * (N + 1) for i in range(N): fa[i + 1] = fa[i] * (i + 1) def order_to_sequence(n, k): S = list(range(n)) res = [] for i in range(1, n + 1): a = fa[n - i] j = k // a res.append(S[j]) S = S[:j] + S[j + 1:] k %= a return res
