問題概要
大きさ $N$ の順列*1 $P,\,Q$ が与えられる．このとき
- $P$ が辞書順で何番目か
- $Q$ が辞書順で何番目か
をそれぞれ求め，それらの差の絶対値を求めよ．
※ 問題へのリンク
制約
- $2 \leqq N \leqq 8$
- $P,\,Q,\,N \in \mathbb{N}$
思考プロセス
- $N$ は高々 $8$ なので，愚直に $N!$ 通りの順列を計算しても大丈夫そう．
- でも，もっと賢い方法を考えたい．そういえば，ProjectEuler 24 と似ている．
- 例えば，$(3,4,1,2)$ を考えると，最上位が $3$ であるため，最上位が $1$ と $2$ のそれぞれ $3!=6$ 通り（計12通り）は排除できる．次に，最上位から2番目の桁を見ると $4$ なので，$31$xx および $32$xx のそれぞれ $2!=2$ 通り（計4通り）は排除できる．そして，最上位から $3$ 番目を見ると $1$ なので，$3412$ の可能性しかなくなり，順番が確定する．よって，$(3,4,1,2)$ は $12+4+0+1=17$ 番目の順列である*2．このようにして，与えられた順列が辞書式で何番目なのかを計算することができる．
- 注意すべき点としては，例えば $(2,4,3,1)$ の場合を考えたとき，最初に $(2-1)\times 3! = 6$ 通りの可能性が排除される．次に，$(4-1)\times 2! = 6$ 通りの可能性が排除されるかというとそうではなく，正しくは $2\times 2!=4$ 通りの可能性が排除される．これは，最上位の桁が $2$ であり，$21$xx または $23$xx の可能性しかないためである．
書いたコード（Python）
def fact(n):
if n==1 or n==0:
return 1
else:
return n*fact(n-1)
def index(n,lis):
for i in range(len(lis)):
if n==lis[i]:
return i
def count(lis):
l = list(range(1,len(lis)+1)) #[1,2,...,n]
ret = 1
for i in range(len(lis)-1):
ret += (index(int(lis[i]),l)) * fact(len(l)-1)
l.remove(lis[i])
return ret
動作例
>>> count([4,1,3,2])
20
