C++でnCr（組み合わせ）の値を計算するプログラム

本記事では、C++を使ってnCr（組み合わせ）の値を計算するプログラムを紹介します。ここで、Cは組み合わせ（Combination）を表し、nは全体の要素数、rはその集合から選び出す要素の数を意味します。

組み合わせとは？

組み合わせとは、与えられた集合から要素を選び出す際に、並び順を考慮しない選択方法のことです。よく混同されやすい「順列」との違いは、順列が要素の「並べ方」を扱うのに対し、組み合わせは単に「選び方」を扱うという点にあります。

例えば、{A, B, C} から2つを選ぶ場合、「AB」と「BA」は順列では別物ですが、組み合わせでは同じ1通りとして数えます。

nCrの計算式

n個の中からr個を選ぶ組み合わせの総数は、次の式で求められます。

nCr = n! / (r! × (n-r)!)

ここで「!」は階乗を表します。例えば 5! = 5 × 4 × 3 × 2 × 1 = 120 です。

入出力例

入力：n = 12, r = 4
出力：12c4 の値は : 495

アルゴリズム

開始
ステップ1 → 階乗を計算する関数を定義する
    int cal_n(int n)
    int temp = 1
    int i = 2 から i <= n まで i を増やしながらループ
        temp = temp * i を設定
    ループ終了
    temp を返す
ステップ2 → nCrを計算する関数を定義する
    int nCr(int n, int r)
        return cal_n(n) / (cal_n(r) * cal_n(n - r))
ステップ3 → main() 内で
    変数 int n = 12, r = 4 を宣言
    nCr(n, r) を出力
終了

C++サンプルコード

#include <bits/stdc++.h>
using namespace std;

// nの階乗を計算する関数
int cal_n(int n){
    int temp = 1;
    for (int i = 2; i <= n; i++)
        temp = temp * i;
    return temp;
}

// nCrを計算する関数
int nCr(int n, int r){
    return cal_n(n) / (cal_n(r) * cal_n(n - r));
}

int main(){
    int n = 12, r = 4;
    cout << "value of " << n << "c" << r << " is :" << nCr(n, r);
    return 0;
}

実行結果

value of 12c4 is :495

補足：大きな数を扱う場合の注意点

上記の実装はシンプルで分かりやすい反面、階乗の値が急激に大きくなるため、int型では n = 13 程度ですぐにオーバーフローしてしまいます。より大きなnを扱いたい場合は、以下の対策が有効です。

• データ型を long long や unsigned long long に変更する
• 乗算と除算を交互に行い、中間値が大きくなりすぎないようにする
• さらに大きな値が必要な場合は、多倍長整数ライブラリ（Boost.Multiprecisionなど）を利用する

競技プログラミングなどでは、答えを素数で割った余りを求める問題も多く、その場合は剰余演算を組み合わせた実装が一般的です。