Pythonで欠損値を含む順列から元の順列の候補番号の合計を求めるプログラム

問題の概要

整数 n が与えられたとき、1 から n までの正の整数を使って作れるすべての順列(並べ替え)を考えます。これらの順列は辞書順に並べられ、先頭から 1、2、…、n! という番号が割り当てられます。その中から一つの順列が「特別な順列」として選ばれますが、この順列のいくつかの値は忘れられており、該当する位置は 0 に置き換えられています。

ここでの課題は、0 の部分を埋めることで元の特別な順列と一致する可能性があるすべての順列を洗い出し、それらの番号を合計することです。計算結果は大きな数になる可能性があるため、10^9 + 7 で割った余りとして返します。

たとえば、入力が input_arr = [0, 2, 0]、n = 3 の場合、出力は 7 になります。このときあり得る順列は [1, 2, 3] と [3, 2, 1] の 2 つです。辞書順で数えると [1, 2, 3] は 2 番目、[3, 2, 1] は 5 番目に相当するため、答えは 5 + 2 = 7 となります。

解決のための手順

この問題は、階乗とモジュラ逆数を組み合わせることで効率的に解くことができます。大まかな流れは次のとおりです。

1. 法として mod = 10^9 + 7 を定義し、2 のモジュラ逆数 i2 = 2^(mod−2) mod mod を求めます。
2. fact リストに、1 から n までの階乗を mod で割った余りとして格納していきます。
3. cnt を input_arr 内に含まれる 0 の個数とします。
4. cnt が 0 の場合(値がすべて分かっている場合)
   • res := 0、seen_list := 空リストで初期化します。
   • input_arr の各要素 x(インデックス i は 1 始まり)について、二分探索により seen_list にソート順を保ったまま x を挿入できる位置 tmp_val を求めます。
   • res に fact[n−i] × (x − 1 − tmp_val) を加算し、mod を取ります。
   • x を seen_list の tmp_val の位置に挿入します。
   • すべての要素を処理したら、res + 1 を返します。
5. cnt が 0 でない場合(欠損値がある場合)
   • ik := cnt のモジュラ逆数(cnt^(mod−2) mod mod)を求めます。
   • miss := サイズ n の True 初期化リストを作成し、input_arr に存在する値 x に対して miss[x−1] := False とします。これで「欠けている値」が特定できます。
   • miss_srtd に欠けている値を昇順で集め、その総和を tmp とします。
   • pre は miss の累積和リストです。
   • s := tmp mod mod × ik mod mod とします。
   • srtdw := 空リスト、res := 0、z := 0、cnt_cu := 0 で初期化します。
   • input_arr の各要素 x(インデックス i は 1 始まり)ごとに以下を処理します。
     • x が非ゼロの場合:l を x を srtdw に挿入できる位置とし、さらに z × (miss_srtd 内での挿入位置) × ik を加算します。p := x − 1 − l を計算し、fact[cnt] を掛けて mod を取ります。x を srtdw に挿入し、cnt_cu に cnt − pre[x] を加算します。
     • x が 0 の場合:l := cnt_cu × ik + z × i2 mod mod とし、p := s − 1 − l に fact[cnt] を掛けて mod を取ります。z を 1 増やします。
     各要素の処理後、res に p × fact[n−i] を加算し、mod を取ります。
   • 最後に (res + fact[cnt]) mod mod を返します。

アルゴリズムのポイント

辞書順における順列の番号は、「各位置でそれより小さい未使用の値の選択肢の数 × 残りの桁数の階乗」の総和に 1 を加えたものとして求められます。値が欠損している場合は、欠損位置に入り得る候補全体に対する寄与をまとめて計算する必要があり、ここでモジュラ逆数による除算が活躍します。二分探索(bisect)を併用することで、全体の計算量は O(n log n) 程度に抑えられます。

Python 実装例

それでは、実際のコードを見てみましょう。

import bisect

def solve(input_arr, n):
    modulo = 10 ** 9 + 7
    i2 = pow(2, modulo-2, modulo)
    fact = [1]
    for x in range(1, n+1):
        fact.append(fact[-1] * x % modulo)

    cnt = input_arr.count(0)

    if not cnt:
        res = 0
        seen_list = []
        for i, x in enumerate(input_arr, 1):
            tmp_val = bisect.bisect(seen_list, x)
            res += fact[n-i] * (x - 1 - tmp_val)
            res %= modulo
            seen_list.insert(tmp_val, x)
        return res + 1
    else:
        ik = pow(cnt, modulo-2, modulo)
        miss = [True] * n
        for x in input_arr:
            if x != 0: miss[x-1] = False
        miss_srtd = []
        tmp = 0
        for i, x in enumerate(miss, 1):
            if x:
                miss_srtd.append(i)
                tmp += i
        pre = [0]
        for x in miss:
            pre.append(pre[-1] + x)
        cnt_cu = 0
        s = tmp % modulo * ik % modulo
        srtdw = []
        res = z = 0
        for i, x in enumerate(input_arr, 1):
            if x:
                l = tmp_val = bisect.bisect(srtdw, x)
                l += z * bisect.bisect(miss_srtd, x) % modulo * ik % modulo
                p = x - 1 - l
                p *= fact[cnt]
                p %= modulo
                srtdw.insert(tmp_val, x)
                cnt_cu += cnt - pre[x]
            else:
                l = cnt_cu
                l *= ik
                l += z * i2 % modulo
                p = s - 1 - l
                p *= fact[cnt]
                p %= modulo
                z += 1
            res += p * fact[n-i] % modulo
            res %= modulo
        return (res + fact[cnt]) % modulo

print(solve([0, 2, 0], 3))

入力

[0, 2, 0], 3

出力

7

このように、欠損した値を含む順列からでも、階乗・累積和・モジュラ逆数を組み合わせることで、元の順列となり得るすべての候補の番号の合計を高速に求めることができます。