C++で集合をk個の部分集合に分割する方法の総数を動的計画法で求める

2つの数 e(要素数) と p(分割数) が与えられたとき、「集合の e 個の要素を p 個の部分集合(パーティション)に分割する方法が全部で何通りあるか」を求めるのがこの問題の目的です。

例1

入力

e=4 p=2

出力

Count of number of ways to partition a set into k subsets are: 7

説明

要素が a・b・c・d の4つである場合、これらを2つのグループに分ける方法は次の7通りあります。

(a)−(b,c,d)、(b)−(a,c,d)、(c)−(a,b,d)、(d)−(a,b,c)、(a,b)−(c,d)、(a,c)−(b,d)、(a,d)−(b,c)

例2

入力

e=2 p=2

出力

Count of number of ways to partition a set into k subsets are: 1

説明

要素が a・b の2つの場合、2つのグループへの分割は (a)−(b) の1通りだけです。

アプローチ：動的計画法(DP)

ここでは動的計画法を利用します。この問題の計算は再帰的な関係(漸化式)で表すことができます。e 個の要素を p 個のグループに分割する方法の数を ways(e, p) とおくと、残りの1個の要素の扱い方によって次の2ケースに分けられます。

• ケース1: e−1 個の要素がすでに p 個のグループに分けられている場合、その方法の数は ways(e−1, p)。残りの1個の要素は既存の p 個のグループのどれに入れてもよいため、p × ways(e−1, p) 通りとなります。
• ケース2: e−1 個の要素が p−1 個のグループに分けられている場合、その方法の数は ways(e−1, p−1)。残りの1個の要素だけで新しい独立したグループを1つ作るため、1 × ways(e−1, p−1) 通りとなります。

以上より、次の漸化式が導かれます。

ways(e, p) = p × ways(e−1, p) + ways(e−1, p−1)

なお、この数は組合せ論で「第2種スターリング数」として知られています。単純な再帰では同じ計算が何度も繰り返されてしまうため、DPテーブルによるメモ化で重複計算を回避します。

アルゴリズムの手順

1. 変数 elements(要素数)と partition(分割数)を入力として受け取ります。
2. 関数 partition_k(int elements, int partition) が2つの値を受け取り、集合を k 個の部分集合に分割する方法の数を返します。
3. 2次元配列 arr[elements + 1][partition + 1] を用意し、ways(e, p) の値を arr[e][p] に格納します。
4. i = 0 ～ elements のループで arr[i][0] = 0 を設定します(分割数が0なら方法の数も0)。
5. j = 0 ～ partition のループで arr[0][j] = 0 を設定します(要素数が0なら方法の数も0)。
6. i = 1 ～ elements、j = 1 ～ i の二重ループで残りの値を順番に埋めていきます。
7. 要素が1個の場合、また x 個の要素を x 個のグループに分ける場合は必ず1通りなので、i == j または j == 1 のときは arr[i][j] = 1 を設定します。
8. それ以外の場合は temp_1 = arr[i−1][j−1]、temp_2 = arr[i−1][j] とし、arr[i][j] = j * temp_2 + temp_1 で更新します。
9. すべてのループが終了した時点で、arr[elements][partition] が全体の方法の数になります。
10. arr[elements][partition] を結果として返します。

C++での実装例

#include<iostream>
using namespace std;
int partition_k(int elements, int partition){
    int arr[elements + 1][partition + 1];
    for(int i = 0; i <= elements; i++){
        arr[i][0] = 0;
    }
    for(int j = 0; j <= partition; j++){
        arr[0][j] = 0;
    }
    for(int i = 1; i <= elements; i++){
        for(int j = 1; j <= i; j++){
            if(j == 1 || i == j){
                arr[i][j] = 1;
            }else{
                int temp_1 = arr[i-1][j-1];
                int temp_2 = arr[i-1][j];
                arr[i][j] = j * temp_2 + temp_1;
            }
        }
    }
    return arr[elements][partition];
}
int main(){
    int elements = 4;
    int partition = 2;
    cout<<"Count of number of ways to partition a set into k subsets are: "<<partition_k(elements, partition);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

Count of number of ways to partition a set into k subsets are: 7

計算量

二重ループによる計算のため時間計算量は O(elements²)、DPテーブルの保持に必要な空間計算量は O(elements × partition) となります。