友達ペアリング問題とは？動的計画法で組み合わせの総数を求める方法

問題の概要

n人の友達からなるグループを考えます。各人はそのままシングルでいるか、他の友達とペアを組むことができます。このとき、全員がシングルまたはペアを組む方法の総数を求めるのが「友達ペアリング問題（Friends Pairing Problem）」です。

なお、ペアを組む2人を p と q とすると、(p, q) と (q, p) は同じペアとして扱います。つまり、ペアの順序は区別しません。

考え方（漸化式の導出）

n人の友達について、シングルまたはペアを組む方法の数を f(n) とします。n番目の人に注目すると、状況は次の2つに分けられます。

• n番目の人がシングルのままの場合： 残りの (n-1) 人の組み合わせを考えればよいので、f(n-1) 通りになります。
• n番目の人が誰かとペアを組む場合： 相手は残りの (n-1) 人のうちの誰かです。相手を1人選ぶと、残りの (n-2) 人の組み合わせは f(n-2) 通りなので、全体で (n-1) × f(n-2) 通りになります。

したがって、次の漸化式が成り立ちます。

f(n) = f(n-1) + (n-1) × f(n-2)

初期条件は f(0) = 0、f(1) = 1、f(2) = 2 です。例えば n = 5 の場合、f(3) = 4、f(4) = 10、f(5) = 26 となり、答えは26通りであることが確認できます。

入力と出力

入力：友達の人数（例：5）
出力：ペアの組み合わせの総数（例：26）

アルゴリズム

countPairs(n)

入力： 友達の人数 n

出力： n人の友達がシングルまたはペアを組む方法の総数

Begin
    サイズ n+1 の配列 pair を定義する
    pair[0] := 0、pair[1] := 1、pair[2] := 2 とする

    i を 3 から n まで繰り返す：
        pair[i] := pair[i-1] + (i-1) * pair[i-2]
    繰り返し終了

    pair[n] を返す
End

C++での実装例

#include <iostream>
using namespace std;

int countPairs(int n) {
    int pairs[n + 1];  // i人のときの組み合わせの数

    // 0〜2人のときの組み合わせはそれぞれ 0〜2 通り
    pairs[0] = 0;
    pairs[1] = 1;
    pairs[2] = 2;

    // 3人目からn人目まで配列を順に埋めていく
    for (int i = 3; i <= n; i++)
        pairs[i] = pairs[i-1] + (i-1) * pairs[i-2];

    return pairs[n];
}

int main() {
    int n;
    cout << "Enter numbers: "; cin >> n;
    cout << "Number of ways to pair " << n << " friends: " << countPairs(n);
}

実行結果

Enter numbers: 5
Number of ways to pair 5 friends: 26

計算量

この動的計画法による解法は、配列を一度走査するだけなので、時間計算量は O(n)、空間計算量は O(n) です。さらに、直前の2つの値だけを変数で保持すれば、空間計算量を O(1) に抑えることも可能です。