異なるN人のグループ分けの総数が知りたい

はじめに

識別可能なN人を任意のグループに分けるとき、その分け方の総数を知りたい。

はじめにPythonを使って力業で数え上げて計算してみた。次に、ベル数を使った計算を行った。

例：4人のグループ分けの総数

a, b, c, dの4人がいたとしよう。分け方は以下の15通り（のはず）。

グループの分け方	メンバーの分け方
oooo	abcd
ooo | o	abc | d
	abd | c
	acd | b
	bcd | a
oo | oo	ab | cd
	ac | bd
	ad | bc
oo|o|o	ab|c|d
	ac|b|d
	ad|b|c
	bc|a|d
	bd|a|c
	cd|a|b
o|o|o|o	a|b|c|d

Pythonで計算してみる

n=4の場合

以下の手順でグループ分けの総数を求めた。

1. 人数分のグループ（空リストn個からなるリスト）を用意する。
2. 一人ずついずれかのグループに配属させる（リスト内リストにappendする）。
3. 全員がいずれかのグループに配属したら、グル－プ分けの状態を整頓する（sorted関数でリスト内要素を並び替える）。
4. 得られたグループ分けを記録する（group_listに追加する）。
5. これ（1~4）をすべての配属パターンについて行う。
6. group_listから重複を取り除く（一度set関数で集合にする）。
7. group_listの要素数を数える（len関数）。

簡単に計算するために標準ライブラリitertoolsに含まれる関数を使う。
docs.python.org

import string
from itertools import product


def main(n):
    assert n <= len(string.ascii_letters), ValueError
    menbers = [s for s in string.ascii_letters[0:n]]
    group_list = []
    assignment_list = product(range(n), repeat=n)
    for assignment in assignment_list:
        groups = [[] for _ in range(n)]
        for e, i in enumerate(assignment):
            groups[i].append(menbers[e])
        groups = '|'.join(sorted([''.join(agroup) for agroup in groups]))
        group_list.append(groups)
    group_list = sorted(list(set(group_list)))
    print(len(group_list))
    print(group_list)
    return


if __name__ == '__main__':
    main(n=4)

実行すると次のようになる。

15
['a|b|c|d', '|ab|c|d', '|ac|b|d', '|ad|b|c', '|a|bc|d', '|a|bd|c', '|a|b|cd', '||abc|d', '||abd|c', '||ab|cd', '||acd|b', '||ac|bd', 
'||ad|bc', '||a|bcd', '|||abcd']

全部で15通りなので、手計算の結果と一致する。

n=8までの場合

N人の場合を計算してみる。値が大きくなると計算時間が非常に大きくなるので、n=8まででテスト。

import string
from itertools import product
import pandas as pd


def calc(n):
    assert n <= len(string.ascii_letters), ValueError
    menbers = [s for s in string.ascii_letters[0:n]]
    group_list = []
    assignment_list = product(range(n), repeat=n)
    for assignment in assignment_list:
        groups = [[] for _ in range(n)]
        for e, i in enumerate(assignment):
            groups[i].append(menbers[e])
        groups = '|'.join(sorted([''.join(agroup) for agroup in groups]))
        group_list.append(groups)
    group_list = sorted(list(set(group_list)))
    print(len(group_list))
    print(group_list)
    return len(group_list)


def main(n):
    df = []
    for k in range(n):
        df.append([k, calc(k)])
    df = pd.DataFrame(df, columns=['n_persons', 'n_groups'])
    df.to_csv('result.csv', index=False)
    return


if __name__ == '__main__':
    main(n=9)

力業でやっているのでまあまあな時間がかかる。出力されるCSVファイルを結果として示す。

n_persons	n_groups
0	1
1	1
2	2
3	5
4	15
5	52
6	203
7	877
8	4140

人数が増えるとグループ分けの総数は爆発的に増える。

計算方法の難点

上で示したPythonコードでは、 通りのグループ分けを計算した後で、重複を取り除くという方法をとっている。

そのため、最初に行うグループ分けの数が、 のときでさえ3.8億通りであり、 が大きくなると計算負荷は爆発的に増加してしまう。

手元のノートパソコンでは、 のときは応答が返ってこなくなってしまったので、計算できなかった。使用するメモリ量を減らすような書き方をしないといけないかもしれない。

ベル数を使って計算する

異なるn個のものをグループに分けるやり方の総数は、ベル数と呼ばれている。

実際、wikiに記載されているベル数を見ると

1, 1, 2, 5, 15, 52, 203, 877, 4140, ...

となっていて、先にPythonで数え上げたときの結果と一致している。

ja.wikipedia.org

グループ分けの一覧ではなく、グループ分けの総数だけが知りたいのであれば、数え上げまでせずにベル数を計算してやれば十分だ。

from scipy.special import comb
import pandas as pd
import matplotlib.pyplot as plt


def bell(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        res = 0
        for k in range(n):
            res += comb(n - 1, k, exact=True) * bell(k)
        return res


def main(n):
    df = []
    for i in range(n + 1):
        df.append([i, bell(i)])
    df = pd.DataFrame(df, columns=['n', 'bell'])
    df.to_csv('bell.csv')

    fig, ax = plt.subplots()
    ax.plot(df['n'], df['bell'], marker='o')
    ax.set_xlabel('n')
    ax.set_ylabel('Bell number')
    fig.tight_layout()
    fig.savefig('bell.jpg', dpi=300)
    return


if __name__ == '__main__':
    main(n=10)

数え上げる方法よりも早く計算できたため、より大きなnに対しても計算が可能になった。