辞書順で何番目問題をpythonで解く方法

2022.11.10
記事内に広告が含まれています。

順列に関する問題で、以下の2つのパターンをpythonで解く方法について解説します。

  1. ある数字列が与えられ、辞書順で何番目か
  2. 先頭からk番目の数字列が何か

どういう問題かイメージできない場合は以下のリンクをご参照ください。

辞書式に並べたとき何番目問題
上野竜生です。数字を並べ替えたり文字を辞書式に並べ替える場合の問題を解説します。 数字の並べ替え 「１」「２」…
math-juken.com

数字列が何番目か答えるコード

ある数字列 L が与えられた際、辞書順で何番目かを求めるコードです。

from math import factorial #x!を計算
def index_of_permutation(L):
    index = 0  #0-indexed
    while len(L)> 1:
        a = len([l for l in L if l<L[0]])
        index = index + a * factorial(len(L) - 1)
        L = L[1:]
    return index

#実行例
print(index_of_permutation([3,2,4,1])) # 15

アルゴリズムの考え方

例えば、[3,2,4,1] が辞書順で何番目かを計算してみます。

  1. 1□□□ の並べ方の場合の数は$\color{red}{3!}$通り
  2. 2□□□ の並べ方の場合の数は$\color{red}{3!}$通り
  3. 3 1□□ の並べ方の場合の数は$\color{blue}{2!}$通り
  4. 3 2 1□ の並べ方の場合の数は$\color{green}{1!}$通り

以上から、

$$2\times \color{red}{3!} \color{black}{+1} \times \color{blue}{2!}\color{black}{+1\times} \color{green}{1!} \color{black}{=15}$$

と計算することができます。

以上の計算方法を任意の正整数に適用できるようにしたのが上のコードです。

コードの挙動の確認

L=[3,2,4,1] の場合を考えてみます。

L = [3,2,4,1] の場合

while の1回目のループです。

この場合、コードの5行目の変数 a は、a = len([2,1])=2 です。

これは 1□□□ および 2□□□ の場合の数を計算していることに対応します。

従って、index = 0 + 2 * factorial(3) = 12 となります。

最後に、L = L[1:] = [2,4,1] と変更します。(先頭が3未満の場合は全て数え上げが終了し、先頭を3に固定する操作に対応します。)

L = [2,4,1] の場合

while の2回目のループです。L[0]=2 の場合を考えると、

a = len([1])=1

これは、3 1□□ の場合の数を計算していることに対応します。

従って、　index = 12 + 1*factrial(2) = 14　となります。

最後に、 L = L[1:] = [4,1] と変更します。(3 2 □□ より前の場合の数は数え上げが完了したことを意味します。)

L = [4,1] の場合

while の3回目のループです。L[0] ＝４の場合を考えると、

a = len([1])=1

これは、3 1 4□ の場合の数を計算していることに対応します。

従って、　index = 14 + 1*factrial(1) = 15　となります。

最後に、 L = L[1:] = [1] と変更します。(3 2 4□ より前の場合の数は数え上げが完了したことを意味します。)

最後に、 3 2 4 □ に対して選べる選択肢が一個しかない(L=[1])ため、3 2 4 1 を得られました。ここい至るまでに計算された index(=15) が答えになります。

先頭からk番目の数字列が何かを求めるコード

def kth_perm(n,k):
    S = list(range(1,n+1)) #[1,2,...,n]の数字列
    rs = []
    for i in range(1,n+1):
        r = k%i
        k //= i
        rs.append(r)
    
    ans = []
    for r in rs[::-1]:
        s = S[r]
        ans.append(s)
        
        S = S[:r] + S[r+1:]
    
    return ans

このアルゴリズムについては、以下の記事にわかりやすく説明されています。

辞書順で N 番目の順列を求める
概要
iilj.github.io

例として、[1,2,3,4]の順列の15番目の数字列を求める場合を考えてみましょう。15という数字は、

$$15 = 4!\times \color{blue}{0}\color{black}{ + 3!\times}\color{blue}{2} \color{black}{+ 2!\times} \color{blue}{1}\color{black}{ + 1!\times} \color{blue}{1} \tag{1}$$

と変形できます。

この式は以下のようにも変形することができます。

$$15 = 1\times( 2\times( 3\times(4\times \color{red}{0}\color{black}{+} \color{red}{2}\color{black}{)+}\color{red}{1}\color{black}{) + }\color{red}{1} \color{black}{) + }\color{red}{0} \tag{2}$$

コードの5,6行目は、この式の赤い部分を取得しています。そして、この赤い数字の部分は(1)式の i!(i=1,2,3,4) の商に対応しています。 i! の商の意味は以下のように解釈できます。

  • 3!(=6)は1□□□, 2□□□の場合の数、すなわち先頭を固定した際の場合の数を意味します。この場合、$2\times 3!=12$より、15番目は3□□□とわかります。

すなわち、

i!の商は数字列 [1,2,...,N ]の何番目(0-indexed) にあるのか?

と対応しています。

まとめ

順列の辞書順で何番目かを求める問題を解くアルゴリズムについてまとめました。

参考になれば幸いです。

コメント