Pythonで0からnまでのnCr値を効率的に求めるプログラム

はじめに

プログラミングでは、nCr(組み合わせの数)を何度も計算する必要がある場面がよくあります。実は、すでに計算した小さな値を保存しておけば、より大きな値を非常に効率的に求めることができます。

具体的には、整数 n が与えられたとき、nC0 から nCn までのすべての値をリストとして求めます。ただし、答えが大きくなりすぎる場合は、10^9 で割った余りを返します。

例えば、入力が n = 6 の場合、出力は [1, 6, 15, 20, 15, 6, 1] となります。

アルゴリズムの考え方

この問題を解く鍵となるのは、次の漸化式です。

nCr = nC(r−1) × (n − r + 1) / r

つまり、直前の値 nC(r−1) が分かれば、そこから次の値 nCr を簡単に計算できます。毎回階乗を計算する必要がないため、計算量を大幅に削減できるのがポイントです。

解法の手順

• items を「1」のみを含むリストとして初期化します(これは nC0 に相当します)
• r を 1 から n まで繰り返します:
  • (items の最後の要素 × (n − r + 1)) ÷ r の商を items の末尾に追加します
  • 末尾から2番目の要素(items[-2])を 10^9 で割った余りに更新します
• items を返します

実装例

以下のコードで実際の動作を確認してみましょう。

def solve(n):
    items = [1]
    for r in range(1,n+1):
        items.append(items[-1]*(n-r+1)//r)
        items[-2] %= 10**9
    return items

n = 6
print(solve(n))

入力

6

出力

[1, 6, 15, 20, 15, 6, 1]

まとめ

この方法では、各値を直前の値から定数時間で導出できるため、全体の計算量は O(n) になります。階乗をそのまま計算する方法と比べても大幅に高速で、桁あふれ対策として剰余を取る処理も組み込まれています。競技プログラミングなどで組み合わせの数を頻繁に求める際にぜひ活用したいテクニックです。