C++で組み合わせと順列を計算する方法をわかりやすく解説

組み合わせと順列とは

組み合わせ（Combination）と順列（Permutation）は、数学の一分野である組合せ論（Combinatorics）に属する概念です。

順列とは、n個の要素の中から、1つずつ・いくつかずつ・あるいはすべてを一度に取り出して並べるときの、異なる並び方の総数のことです。並べる順序が結果に影響する点が特徴です。

一方、組み合わせとは、同じくn個の要素から1つずつ・いくつかずつ・すべてを取り出して選ぶときの、異なる選び方の総数です。順序は考慮されないため、順列よりも数が少なくなります。

計算式

順列の数

n個の要素全体からr個の要素を並べるときの順列の数は、次の公式で求められます。

P(n, r) = n! / (n − r)!

組み合わせの数

n個の要素全体からr個の要素を選ぶときの組み合わせの数は、次の公式で求められます。

C(n, r) = n! / (r! × (n − r)!)

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

C++での実装例

以下は、C++で組み合わせと順列を計算するプログラムの例です。

#include <iostream>
using namespace std;

// 階乗を再帰的に計算する関数
int fact(int n) {
    if (n == 0 || n == 1)
        return 1;
    else
        return n * fact(n - 1);
}

int main() {
    int n, r, comb, per;

    cout << "Enter n : ";
    cin >> n;
    cout << "\nEnter r : ";
    cin >> r;

    // 組み合わせ：C(n, r) = n! / (r! * (n-r)!)
    comb = fact(n) / (fact(r) * fact(n - r));
    cout << "\nCombination : " << comb;

    // 順列：P(n, r) = n! / (n-r)!
    per = fact(n) / fact(n - r);
    cout << "\nPermutation : " << per;

    return 0;
}

実行結果

上記プログラムを実行すると、次のような出力が得られます。

Enter n : 5
Enter r : 3
Combination : 10
Permutation : 60

プログラムの解説

このプログラムのポイントは以下の通りです。

• fact関数：引数nの階乗を再帰的に計算します。nが0または1のときは1を返し、それ以外の場合は「n × fact(n−1)」を返すことで、再帰的に階乗を求めます。
• 組み合わせの計算：「fact(n) / (fact(r) * fact(n-r))」という式で、公式 C(n, r) をそのまま実装しています。
• 順列の計算：「fact(n) / fact(n-r)」という式で、公式 P(n, r) を実装しています。

入力例では n=5、r=3 としたため、組み合わせは 10（5! / (3! × 2!)）、順列は 60（5! / 2!）と正しく計算されています。

注意点

int型で扱える値には上限があるため、nが大きくなると階乗の値がオーバーフローして誤った結果になります。大きな数を扱う場合は、long long型を使用するか、多倍長整数ライブラリの利用を検討してください。