オーバーフローを防ぎつつ組み合わせ（nCr）を計算するテクニック

Aru

組み合わせの数であるnCr（コンビネーション）をプログラムで計算したくなることがあります。競プロやシミュレーションの実装などで、よく登場する計算です。しかし、愚直に階乗を使って計算しようとすると、意外とすぐにオーバーフローの壁に突き当たります。

今回は、計算の順番を少し工夫するだけで、このオーバーフローをきれいに回避できるテクニックを試してみました。

Contents

はじめに
- なぜ愚直な計算はオーバーフローするのか
オーバフローを起こさない計算方法
- 計算順序を工夫する：「掛けて割る」を繰り返す
- 実装コード
まとめ

はじめに

例えば、 $20C_{10}$ という計算を考えます。答えは $184,756$ であり、32ビット整数型にも十分に収まる大きさです。

それなのに、計算結果がおかしくなることがあります。これは、計算途中で発生するオーバフローが原因です。

なぜ愚直な計算はオーバーフローするのか

組み合わせの数 $nC_r$ の定義式は以下の通りです。

$$
nC_r = \frac{n!}{r!(n-r)!}
$$

また、分子と分母を整理して、次のような式に変形することもできます。

$$
nC_r = \frac{n \times (n-1) \times \dots \times (n-r+1)}{r \times (r-1) \times \dots \times 1}
$$

この式を、そのままプログラムコードにする場合、分子と分母を別々に計算し、最終的に分母で割るという方法が最も簡単です。しかし、分子の計算結果を考えるとこのやり方には問題があることに気づきます。

$_{20}C_{10}$ をこの式で計算する場合、分子は次のようになります。

$$
20 \times 19 \times 18 \times \dots \times 11 = 670,442,572,800
$$

この値は、一般的な32ビット符号付き整数型（最大値は約21億）の上限を大きく超えています。つまり、分子の計算がオーバーフローしてしまうのです。

このため、最終的な計算結果である $_{20}C_{10} = 184,756$$ は非常に小さいにもかかわらず、計算結果が合わなくなってしまいます。

Python のように多倍長整数をサポートしている言語であればエラーなく計算できます。ただ、大きな中間値は、メモリや演算処理時間で不利となり、やはり避けたいです。

オーバフローを起こさない計算方法

計算順序を工夫する：「掛けて割る」を繰り返す

このオーバーフローを防ぐためのアプローチとして、分子をすべて掛け合わせてから分母で割るのではなく、1ステップずつ「掛けて割る」を交互に行う方法があります。

直感的に分かりやすいように、分子を大きい方から（ $20 \times 19 \times 18 \dots $ ）、分母を小さい方から（ $1 \times 2 \times 3 \dots$）順にペアにして「掛けて割る」を繰り返していきます。

具体的には、初期値を 1 として、ループの中で以下の計算を繰り返します。

$$
C \leftarrow C \times (n – i + 1) / i
$$

プログラミングに慣れた人は「割り算を都度行うと途中で割り切れずに演算誤差が出てしまうのではないか？」という疑問がでるかもしれません。でも、実は、必ず割り切れるのです！

ここが面白いところで、例えばi=3まで考えると、

$$
\frac{20 \times 19 \times 18}{1 \times 2 \times 3}
$$

となります。この数式を見ると、18と20が2で割れ、18が3で割れることがわかります。このように、必ず割り切れる数値が含まれるのが、この方法の面白い部分です。

これは「$i$個の連続した数値の中には、必ず$i$で割れる数値が1つは含まれる」という数学的な事実によるものです。

$_{20}C_{10}$の例

実例として、$_{20}C_{10}$ の計算を考えてみます。

この計算では、初期値を 1 として、以下のステップを繰り返します。

まず $i = 1$ のとき、分子の最大値である $20$ を掛けて、分母の$1$ で割ります。式にすると $20 / 1 = 20$ になり、これは当然割り切れます。

次に $ i = 2$ のとき、これまでの値に $19$ を掛けて $2$ で割ります。この時点で計算している式は、分子が $20 \times 19 $、分母が$1 \times 2 $ となり、全体では$(20 \times 19) / 2 $になります。ここで分子に注目すると、連続する2つの整数の積であるため、どちらか一方は必ず $ 2 $ の倍数（偶数）です。今回の場合は $20$ が偶数であり、これが分母の $ 2 $ で必ず割り切れるため、結果は整数（ $ 190 $ ）になります。

さらに $i = 3$ のとき、前の結果に$ 18 $ を掛けて$ 3$ で割ります。この時点で計算している式は、分子が $20 \times 19 \times 18 $ 、分母が $ 1 \times 2 \times 3 $ となり、全体では$(20 \times 19 \times 18) / 6 $ になります。分子は連続する3つの整数の積です。連続する3つの整数の中には、必ず $3$ の倍数が含まれており、同時に $2$ の倍数（偶数）も含まれます。

今回の例では、 $18$ が $ 3$ の倍数であり、 $ 20 $ が偶数です。

このように、分母のすべての構成要素（因数である $ 2$ や $ 3$ ）を打ち消す「割る数」が、分子の積の中に必ず含まれています。

そのため、分子は分母の $ 1 \times 2 \times 3 = 6 $で絶対に割り切れます。

実際、 $ 190 \times 18 / 3 = 1140 $となり、余りは発生しません。

一般化すると、ループの $ i $ ステップ目が終わった時点での値は、分子が「連続する $ i $ 個の整数の積」であり、分母が「 $ i! $ （ $ i $ の階乗）」になっています。

連続する $ i $ 個の整数を掛け合わせるということは、その中には必ず $ i $ の倍数、 $ i-1$ の倍数、……そして偶数（ $2$ の倍数）といった、分母の階乗を構成する「割る数（の因数）」がすべて過不足なく含まれていることになります。

したがって、毎ステップの掛け算の後に $ i$ で割る処理は、常に余りなく綺麗に割り切れることが保証されています。

この性質のおかげで、小数を一切経由せず、常に整数型の範囲内で安全に計算を進めることができます。

実装コード

このテクニックを使って、GoとPythonで実装してみました。

まずはGoの実装例です。

package main

import "fmt"

func nCr(n, r int) int {
	if r < 0 || r > n {
		return 0
	}
	// nCr = nC(n-r) なので、計算回数を減らすために小さい方を r とする
	if r > n-r {
		r = n - r
	}

	ret := 1
	for i := 1; i <= r; i++ {
		ret = ret * (n - i + 1) / i
	}
	return ret
}

func main() {
	fmt.Println("20C10 = ", nCr(20, 10))
}

計算結果は正しく 184756 と表示されます。

コード中の変数の推移を見ると、上で説明した通り、途中の計算値が常にその時点での組み合わせの数（ $ 20C_1 $, $ 20C_2 $, $ 20C_3 $… ）になっており、最終的な答えである $ 184756 $ を超えることなく計算が進んでいることがわかります。

ちなみに、int64であれば$_{70}C_{35}くらいまでは正しく計算できます。

Pythonで書く場合は、整数除算演算子 `//` を使うことで、型エラーを防ぎつつ同様に実装できます。

def nCr(n: int, r: int) -> int:
    if r < 0 or r > n:
        return 0
    if r > n - r:
        r = n - r
        
    ans = 1
    for i in range(1, r + 1):
        ans = ans * (n - i + 1) // i
    return ans

# 動作確認
print(f"20C10 = {nCr(20, 10)}")