C++でn人をペアにする組み合わせの総数を求める方法

問題概要

n人の人たちがいる場面を考えます。それぞれの人は「単独で行動する」か「誰かとペアを組む」かのどちらかを選べます。このとき、これらの人々をグループ分けする方法が全部で何通りあるのかを求めるのが、本記事のテーマです。

入出力の例

入力：3

出力：4

説明：[{1}, {2}, {3}]、[{1, 2}, {3}]、[{1}, {2, 3}]、[{1, 3}, {2}]
　　　この4通りが、3人を分類するすべての方法です。

入力：6

出力：76

解法のアプローチ

この問題は、次の漸化式（対合数・電話番号と呼ばれる数列）を利用することで効率よく解くことができます。

A[n] = A[n-1] + (n-1) * A[n-2]

この式の意味は次のとおりです。

• n番目の人が単独の場合： 残りの(n-1)人の組み合わせ方は A[n-1] 通り。
• n番目の人がペアを組む場合： 相手は残り(n-1)人の中から選べ、そのほかの(n-2)人の組み合わせ方は A[n-2] 通り。よって全体で (n-1) × A[n-2] 通りになります。

この2つのケースを足し合わせることで、A[n] の値が求まります。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int countPairings(int n){
    int A[n + 1]; // 答えを格納する配列
    A[1] = 1; // 初期値
    A[2] = 2; // 初期値
    for (int i = 3; i <= n; i++) { // 漸化式を使って答えを計算
        A[i] = A[i - 1] + (i - 1) * A[i - 2];
    }
    return A[n]; // 答えを返す
}
int main(){
    int n = 6;
    cout << countPairings(n);
    return 0;
}

実行結果

76

コードの解説

上記のコードでは、まず配列 A の初期値として A[1] = 1、A[2] = 2 を設定しています。その後、forループで i を3から n まで順に処理しながら、漸化式 A[i] = A[i-1] + (i-1) × A[i-2] を適用していきます。すでに計算済みの直前の2つの値を配列から参照するため、重複した計算が発生せず、計算量 O(n) で非常に高速に答えを導き出せるのが特徴です。

まとめ

本記事では、n人をペアまたは単独に分類する方法の総数を求める問題を取り上げました。漸化式を活用したシンプルな動的計画法のアプローチにより、この問題を効率的に解くことができます。紹介したプログラムはC++で記述しましたが、同じロジックはC言語、Java、Pythonなど他の言語でも同様に実装可能です。皆さんの競技プログラミングや学習の一助となれば幸いです。