Pythonで要素の順序を保ったまま2つのリストをマージする方法の数を求めるプログラム

2つのリスト nums1 と nums2 があるとします。ここでの制約は、マージを行う際に各リスト内の要素の相対的な順序が変わらないことです。例えば、要素が [1,2,3] と [4,5,6] の場合、[1,4,2,3,5,6] や [1,2,3,4,5,6] などが有効なマージ結果となります。他にも有効なマージ順序は存在します。

リストのサイズをそれぞれ N と M としたとき、有効なマージ済みリストを作成できる方法の総数を求める必要があります。答えが非常に大きくなる場合は、10^9 + 7 で割った余りを返してください。

例えば、入力が N = 5、M = 3 の場合、出力は 56 になります。

解法のアプローチ

この問題は実は「組み合わせ」の問題として捉えることができます。N + M 個のスロットの中から、どの位置に片方のリストの要素を配置するかを選ぶことで、残りの位置には自動的にもう一方のリストの要素が入ります。したがって、答えは二項係数 C(N+M, M)、つまり (N+M)! / (N! × M!) で表されます。

この考え方に基づき、以下の手順で計算を行います。

• ret を 1 で初期化する
• i を N+1 から N+M までループし、ret に i を掛けていく(分子の計算)
• i を 1 から M までループし、ret を i で割っていく(分母の計算)
• ret を 10^9 + 7 で割った余りを返す

実装例

理解を深めるために、以下の実装例を見てみましょう。

def solve(N, M):
   ret = 1
   for i in range(N + 1, N + M + 1):
      ret *= i
   for i in range(1, M + 1):
      ret //= i
   return ret % (10**9 + 7)

N = 5
M = 3
print(solve(N, M))

入力

5, 3

出力

56

補足

N = 5、M = 3 の場合、C(8, 3) = 8! / (5! × 3!) = 56 となり、正しく 56 が出力されていることが確認できます。なお、整数除算(//)を使用しているため、途中段階でも値は常に整数として保持され、精度の問題が発生しません。ただし、大きな N と M に対しては、乗算と除算を交互に行うか、モジュラ逆元を利用することでオーバーフローやパフォーマンスの問題を回避できます。