m 個の整数 1, 2, ..., m の順列を考えます。このとき、i 番目 (先頭要素が 1 番目) の要素が整数 i ではない順列を「完全順列」といいます。1 から m までの整数値で完全順列を生成する関数 derangement(m) を定義してください。
derangement(3) => (画面に出力) [2 3 1] [3 1 2] derangement(4) => (画面に出力) [2 1 4 3] [2 3 4 1] [2 4 1 3] [3 1 4 2] [3 4 1 2] [3 4 2 1] [4 1 2 3] [4 3 1 2] [4 3 2 1]
完全順列の総数を「モンモール数 (Montmort number)」といいます。モンモール数は次の漸化式で求めることができます。
モンモール数を多倍長整数 (use bigint) で求める関数 montmort_number を定義してください。
montmort_number(1) => 0 montmort_number(2) => 1 montmort_number(3) => 2 montmort_number(4) => 9 montmort_number(5) => 44 montmort_number(6) => 265 montmort_number(7) => 1854 montmort_umber(10) => 1334961 montmort_number(20) => 895014631192902121 montmort_number(30) => 97581073836835777732377428235481 montmort_number(40) => 300158458444475693321518926221316715906770469041 montmort_number(50) => 11188719610782480504630258070757734324011354208865721592720336801
バランスの取れた n 対のカッコ列を生成する高階関数 kakko(n) を定義してください。カッコ列は ( と ) からなる列のことで、バランスが取れているカッコ列は、右カッコで閉じることができる、つまり右カッコに対応する左カッコがある状態のことをいいます。たとえば n = 1 の場合、( ) はバランスの取れたカッコ列ですが、) ( はバランスが取れていません。
kakko(3) => (画面に出力) ((())) (()()) (())() ()(()) ()()() kakko(4) => (画面に出力) (((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()()
バランスの取れた n 対のカッコ列の総数を多倍長整数 (use bigint) で求める関数 kakko_num(n) を定義してください。
kakko_num(1) => 1 kakko_num(2) => 2 kakko_num(3) => 5 kakko_num(4) => 14 kakko_num(5) => 42 kakko_num(6) => 132 kakko_num(7) => 429 kakko_num(8) => 1430 kakko_num(9) => 4862 kakko_num(10) => 16796 kakko_num(30) => 3814986502092304 kakko_num(50) => 1978261657756160653623774456 kakko_num(100) => 896519947090131496687170070074100632420837521538745909320
整数 n を 1 以上の自然数の和で表すことを考えます。これを「整数の分割」といいます。整数を分割するとき、同じ自然数を何回使ってもかまいませんが、並べる順序が違うだけのものは同じ分割とします。簡単な例を示します。
n = 6
6 分割 : 1 + 1 + 1 + 1 + 1 + 1
5 分割 : 1 + 1 + 1 + 1 + 2
4 分割 : 1 + 1 + 1 + 3
1 + 1 + 2 + 2
3 分割 : 1 + 1 + 4
1 + 2 + 3
2 + 2 + 2
2 分割 : 1 + 5
2 + 4
3 + 3
1 分割 : 6
6 の場合、分割の仕方は 11 通りあります。この数を「分割数」といいます。自然数 n の分割数を多倍長整数 (use bigint) で求める関数 partition_number(n) を定義してください。
partition_number(1) => 1 partition_number(2) => 2 partition_number(3) => 3 partition_number(4) => 5 partition_number(5) => 7 partition_number(6) => 11 partition_number(7) => 15 partition_number(8) => 22 partition_number(10) => 42 partition_number(50) => 204226 partition_number(1000) => 24061467864032622473692149727991
整数 n の分割の仕方をすべて求める高階関数 partition_of_int(n) を定義してください。
partition_of_int(6) => (画面に出力) [6] [5 1] [4 2] [4 1 1] [3 3] [3 2 1] [3 1 1 1] [2 2 2] [2 2 1 1] [2 1 1 1 1] [1 1 1 1 1 1]
スライスで表した集合 ls を分割することを考えます。たとえば、集合 [1 2 3] は次のように分割することができます。
1 分割 : [[1 2 3]] 2 分割 : [[1 2] [3]], [[1 3] [2]], [[1] [2 3]] 3 分割 ; [[1] [2] [3]]
このように、分割した集合 xs は元の集合 ls の部分集合になります。分割した部分集合の積は空集合になり、分割した部分集合のすべての和を求めると元の集合になります。
ls の分割の仕方をすべて求める関数 parititon_of_set(ls) を定義してください。
partition_of_set([1, 2, 3]) => (画面に出力) [[1 2 3]] [[1 2] [3]] [[1 3] [2]] [[1] [2 3]] [[1] [2] [3]] partition_of_set([1, 2, 3, 4]) => (画面に出力) [[1 2 3 4]] [[1 2 3] [4]] [[1 2 4] [3]] [[1 2] [3 4]] [[1 2] [3] [4]] [[1 3 4] [2]] [[1 3] [2 4]] [[1 3] [2] [4]] [[1 4] [2 3]] [[1] [2 3 4]] [[1] [2 3] [4]] [[1 4] [2] [3]] [[1] [2 4] [3]] [[1] [2] [3 4]] [[1] [2] [3] [4]]
集合を分割する方法の総数を「ベル数 (Bell Number)」といい、次の漸化式で求めることができます。
ベル数を多倍長整数 (use bigint) で求める関数 bell_number(n) を定義してください。
bell_number(0) => 1 bell_number(1) => 1 bell_number(2) => 2 bell_number(3) => 5 bell_number(4) => 15 bell_number(5) => 52 bell_number(10) => 115975 bell_number(20) => 51724158235372 bell_number(40) => 157450588391204931289324344702531067 bell_number(60) => 976939307467007552986994066961675455550246347757474482558637
k 個の要素をもつ集合 ls を要素数が等しい m 個の部分集合に分割することを考えます。部分集合の要素数 n は k / m になります。分割の仕方をすべて求める高階関数 group_partition(n, m, ls) を定義してください。
group_partition(2, 2, [1, 2, 3, 4]) => (画面に表示) [[1 2] [3 4]] [[1 3] [2 4]] [[1 4] [2 3]] group_partition(2, 3, [1, 2, 3, 4, 5, 6]) => (画面に表示) [[1 2] [3 4] [5 6]] [[1 2] [3 5] [4 6]] [[1 2] [3 6] [4 5]] [[1 3] [2 4] [5 6]] [[1 3] [2 5] [4 6]] [[1 3] [2 6] [4 5]] [[1 4] [2 3] [5 6]] [[1 5] [2 3] [4 6]] [[1 6] [2 3] [4 5]] [[1 4] [2 5] [3 6]] [[1 4] [2 6] [3 5]] [[1 5] [2 4] [3 6]] [[1 6] [2 4] [3 5]] [[1 5] [2 6] [3 4]] [[1 6] [2 5] [3 4]]
集合を group_partition で分割するとき、その仕方の総数を多倍長整数 (use bigint) で求める関数 group_Partition_Number(n, m) を定義してください。
引数 n は部分集合の要素数、m は部分集合の個数です。
group_partition_number(2, 2) => 3 group_partition_number(2, 3) => 15 group_partition_number(3, 3) => 280 group_partition_number(3, 4) => 15400 group_partition_number(3, 5) => 1401400
リスト : 完全順列
use strict;
use warnings;
# $n と等しい要素があるか
sub member {
my ($n, $xs) = @_;
foreach my $x (@$xs) {
return 1 if $n == $x;
}
0;
}
sub perm_sub {
my ($n, $xs) = @_;
if (@$xs == $n) {
print "@$xs\n";
} else {
for (my $i = 1; $i <= $n; $i++) {
if ($i != @$xs + 1 && !member($i, $xs)) {
push @$xs, $i;
perm_sub($n, $xs);
pop @$xs;
}
}
}
}
sub derangement {
my $n = shift;
perm_sub($n, []);
}
derangement(3);
derangement(4);
実際の処理は関数 perm_sub で行います。1 から $n までの数字を $n 個選ぶ順列を生成する処理で、数字 $i が @$xs + 1 と等しい場合は数字 $i を選択しません。@$xs が $n と等しい場合は $n 個の数字を選んだので $xs を表示します。これで完全順列を生成することができます。
リスト : 完全順列の総数
use strict;
use warnings;
use bigint;
sub montmort_number {
my $n = shift;
if ($n == 1) {
0;
} elsif ($n == 2) {
1;
} else {
($n - 1) * (montmort_number($n - 1) + montmort_number($n - 2));
}
}
# 別解
sub montmort_number2 {
my $n = shift;
my ($a, $b) = (0, 1);
for (my $i = 1; $i < $n; $i++) {
my $c = $b;
$b = ($i + 1) * ($a + $b);
$a = $c;
}
$a;
}
for (my $i = 1; $i <= 10; $i++) {
print montmort_number($i), "\n";
}
for (my $i = 10; $i <= 50; $i += 10) {
print montmort_number2($i), "\n";
}
関数 montmort_number は公式をそのままプログラムしただけです。二重再帰になっているので、実行速度はとても遅くなります。これを繰り返しに変換すると別解のようになります。考え方はフィボナッチ数列と同じです。変数 $a に $i 番目の値を、$b に $i + 1 番目の値を保存しておきます。すると、$i + 2 番目の値は ($i + 1) * ($a + $b) で計算することができます。あとは、$b の値を $a に、新しい値を $b にセットして処理を繰り返すだけです。
リスト : カッコ列の生成
use strict;
use warnings;
sub kakko_sub {
my ($x, $y, $m, $a) = @_;
if ($x == $y && $x == $m) {
print $a, "\n";
} else {
if ($x < $m) {
kakko_sub($x + 1, $y, $m, $a . "(");
}
if ($y < $x) {
kakko_sub($x, $y + 1, $m, $a . ")");
}
}
}
sub kakko {
my $m = shift;
kakko_sub(0, 0, $m, "");
}
kakko(3);
kakko(4);
カッコ列の生成は簡単です。関数 kakko_sub の引数 $x が左カッコの個数、引数 $y が右カッコの個数を表します。引数 $a は累積変数でカッコ列を表す文字列です。
バランスの取れたカッコ列の場合、$x, $y, $m には $y <= $x <= $m の関係が成り立ちます。$x == $y == $m の場合、カッコ列がひとつ完成しました。print で $a を表示します。そうでなければ、kakko_sub を再帰呼び出しします。$x < $m であれば左カッコを追加し、$y < $x であれば右カッコを追加します。これでカッコ列を生成することができます。
カタラン数 - Wikipedia によると、カッコ列の総数は「カタラン数 (Catalan number)」になるとのことです。カタラン数は次に示す公式で求めることができます。
これをそのままプログラムしてもいいのですが、それではちょっと面白くないので別な方法でプログラムを作ってみましょう。カタラン数は次に示す経路図において、A から B までの最短距離の道順を求めるとき、対角線を超えないものの総数に一致します。
Ｂ Ｂ
┌─┬─┬─┬─┐ ┌─┬─┬─０─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─┼─０─５─14
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ├─０─２─５─９
│ │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┤ ０─１─２─３─４
│ │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┘ １─１─１─１─１
Ａ Ａ
図 : 道順の総数の求め方
A からある地点にいたる最短距離の道順の総数は、左隣と真下の地点の値を足したものになります。一番下の地点は 1 で、対角線を越えた地点は 0 になります。あとは下から順番に足し算していけば、A から B までの道順の総数を求めることができます。上図の場合はカラタン数 Ｃ4 に相当し、その値は 14 となります。
プログラムはスライスを使うと簡単です。次の図を見てください。
0 : [1, 1, 1, 1, 1] 1 : [1, 1, 1, 1, 1,] 2 : [1, 1, 1+1=2, 2+1=3, 3+1=4] => [1, 1, 2, 3, 4] 3 : [1, 1, 2, 3+2=5, 5+4=9] => [1, 1, 2, 5, 9] 4 : [1, 1, 2, 5, 5+9=14] => [1, 1, 2, 5, 14]
上図は Ｃn (n = 4) を求める場合です。大きさが n + 1, 要素の値が 1 のベクタを用意します。n = 0, 1 の場合は n 番目の要素をそのまま返します。n が 2 よりも大きい場合、変数 i を 2 に初期化して、i - 1 番目以降の要素の累積和を求めます。
たとえば i = 2 の場合、2 番目の要素は 1 番目の要素と自分自身を加算した値 2 になります。3 番目の要素は 2 番目の要素と自分自身を足した値 3 になり、4 番目の要素は 3 + 1 = 4 になります。次に i を +1 して同じことを繰り返します。3 番目の要素は 2 + 3 = 5 になり、4 番目の要素は 5 + 4 = 9 になります。i = 4 のとき、4 番目の要素は 5 + 9 = 14 となり、Ｃ4 の値を求めることができました。
プログラムは次のようになります。
リスト : カッコ列の総数
use strict;
use warnings;
use bigint;
sub kakko_num {
my $n = shift;
my @table = ();
for (my $i = 0; $i <= $n; $i++) {
push @table, 1;
}
for (my $i = 2; $i <= $n; $i++) {
for (my $j = $i; $j <= $n; $j++) {
$table[$j] += $table[$j - 1];
}
}
return $table[$n]
}
for (my $i = 1; $i <= 10; $i++) {
print kakko_num($i), "\n";
}
for (my $i = 20; $i <= 50; $i += 10) {
print kakko_num($i), "\n";
}
説明したことをそのままプログラムしただけなので、とくに難しいところはないと思います。
6 の場合、分割の仕方は上図のように 11 通りあります。分割の仕方を列挙する場合、整数 n から k 以下の整数を選んでいくと考えてください。まず、6 から 6 を選びます。すると、残りは 0 になるので、これ以上整数を分割することはできません。次に、6 から 5 を選びます。残りは 1 になるので、1 を選ぶしか方法はありません。
次に、4 を選びます。残りは 2 になるので、2 から 2 以下の整数を分割する方法になります。2 から 2 を選ぶと残りは 0 になるので 2 が得られます。1 を選ぶと残りは 1 になるので、1 + 1 が得られます。したがって、4 + 2, 4 + 1 + 1 となります。同様に、6 から 3 を選ぶと、残りは 3 から 3 以下の整数を選ぶ方法になります。
6 から 2 以下の整数を選ぶ方法は、残り 4 から 2 以下の整数を選ぶ方法になり、そこで 2 を選ぶと 2 から 2 以下の整数を選ぶ方法になります。1 を選ぶと 4 から 1 以下の整数を選ぶ方法になりますが、これは 1 通りしかありません。最後に 6 から 1 を選びますが、これも 1 通りしかありません。これらをすべて足し合わせると 11 通りになります。
─┬─ 6 : 6
│
├─ 5 ─ 1 : 5 + 1
│
├─ 4 ┬ 2 : 4 + 2
│ │
│ └ 1 ─ 1 : 4 + 1 + 1
│
├─ 3 ┬ 3 : 3 + 3
│ │
│ ├ 2 ─ 1 : 3 + 2 + 1
│ │
│ └ 1 ─ 1 ─ 1 : 3 + 1 + 1 + 1
│
├─ 2 ┬ 2 ┬ 2 : 2 + 2 + 2
│ │ │
│ │ └ 1 ─ 1 : 2 + 2 + 1 + 1
│ │
│ └ 1 ─ 1 ─ 1 ─ 1 : 2 + 1 + 1 + 1 + 1
│
└─ 1 ─ 1 ─ 1 ─ 1 ─ 1 ─ 1 : 1 + 1 + 1 + 1 + 1 + 1
図 : 整数 6 の分割
整数 n を k 以下の整数で分割する総数を求める関数を p(n, k) とすると、p(n, k) は次のように定義することができます。
たとえば、p(6, 6) は次のように計算することができます。
p(6, 6) => p(0, 6) + p(6, 5)
=> 1 + p(1, 5) + p(6, 4)
=> 1 + 1 + p(2, 4) + p(6, 3)
=> 1 + 1 + 2 + 7
=> 11
p(2, 4) => p(-2, 4) + p(2, 3)
=> 0 + p(-1, 3) + p(2, 2)
=> 0 + 0 + p(0, 2) + p(2, 1)
=> 0 + 0 + 1 + 1
=> 2
p(6, 3) => p(3, 3) + p(6, 2)
=> p(0, 3) + p(3, 2) + p(4, 2) + p(6, 1)
=> 1 + p(1, 2) + p(3, 1) + p(2, 2) + p(4, 1) + 1
=> 1 + 1 + 1 + p(0, 2) + p(2, 1) + 1 + 1
=> 1 + 1 + 1 + 1 + 1 + 1 + 1
=> 7
分割数を求める関数 partition_number は、関数 p(n, k) を使うと次のようにプログラムすることができます。
リスト : 分割数
use strict;
use warnings;
use bigint;
sub part_num {
my ($n, $k) = @_;
if ($n < 0 || $k < 1) {
0;
} elsif ($n <= 1 || $k == 1) {
1;
} else {
part_num($n - $k, $k) + part_num($n, $k - 1);
}
}
sub partition_number {
my $n = shift;
part_num($n, $n);
}
for (my $i = 1; $i <= 10; $i++) {
print partition_number($i), "\n";
}
関数 part_num は p(n, k) の定義をそのままプログラムしただけです。ただし、このプログラムは二重再帰で何度も同じ値を求めているため実行速度はとても遅くなります。
動的計画法を使うと、大きな値でも高速に計算することができます。次の図を見てください。
k 1 : [1, 1, 1, 1, 1, 1, 1] 2 : [1, 1, 1+1=2, 1+1=2, 2+1=3, 2+1=3, 3+1=4] => [1, 1, 2, 2, 3, 3, 4] 3: [1, 1, 2, 1+2=3, 1+3=4, 2+3=5, 3+4=7] => [1, 1, 2, 3, 4, 5, 7] 4: [1, 1, 2, 3, 1+4=4, 1+5=6, 2+7=9] => [1, 1, 2, 3, 5, 6, 9 5: [1, 1, 2, 3, 5, 1+6=7, 1+9=10] => [1, 1, 2, 3, 5, 7, 10] 6: [1, 1, 2, 3, 5, 7, 10+1=11] => [1, 1, 2, 3, 5, 7, 11]
大きさ n + 1 のスライスを用意します。スライスの添字が n を表していて、p(n, 1) から順番に値を求めていきます。p(n, 1) の値は 1 ですから、スライスの要素は 1 に初期化します。次に、p(n, 2) の値を求めます。定義により p(n, 2) = p(n - 2, 2) + p(n, 1) なので、2 番目以降の要素に n - 2 番目の要素を加算すれば求めることができます。あとは、k の値をひとつずつ増やして同様の計算を行えば p(n, n) の値を求めることができます。
プログラムは次のようになります。
リスト : 分割数 (動的計画法)
sub partition_number2 {
my $n = shift;
my @a = ();
for (my $i = 0; $i <= $n; $i++) {
push @a, 1;
}
for (my $k = 2; $k <= $n; $k++) {
for (my $m = $k; $m <= $n; $m++) {
$a[$m] += $a[$m - $k];
}
}
$a[$n];
}
説明をそのままプログラムしただけなので、とくに難しいところはないと思います。
リスト : 整数の分割
use strict;
use warnings;
sub part_int {
my ($n, $k, $a) = @_;
if ($n == 0) {
print "@$a\n";
} elsif ($n == 1 || $k == 1) {
print "@$a " if @$a;
while ($n-- > 0) {
print "1 ";
}
print "\n";
} else {
if ($n - $k >= 0) {
push @$a, $k;
part_int($n - $k, $k, $a);
pop @$a;
}
part_int($n, $k - 1, $a)
}
}
sub partition_of_int {
my $n = shift;
part_int($n, $n, []);
}
partition_of_int(5);
partition_of_int(6);
基本的な考え方は partition_number と同じです。関数 part_int は選んだ数値を累積変数 $a の配列に格納していくだけです。$n が 0 の場合は $a を表示し、$n が 1 の場合は $a に 1 を追加してから表示します。$k が 1 の場合は $a を表示した後、1 を $n 個表示します。
集合を分割するアルゴリズムは簡単です。たとえば、n -1 個の要素 x1, ..., xn-1 を持つ集合を分割したところ、i 個の部分集合 S1, ..., Si が生成されたとしましょう。ここに、n 番目の要素 xn を追加すると、要素が n 個の集合を分割することができます。
新しい要素を追加する場合は次に示す手順で行います。
簡単な例を示しましょう。次の図を見てください。
[] ─ [[1]] ─┬─ [[1 2]] ─┬─ [[1 2 3]]
│ │
│ └─ [[1 2] [3]]
│
└─ [[1] [2]] ─┬─ [[1 3] [2]]
│
├─ [[1] [2 3]]
│
└─ [[1] [2] [3]]
図 : 集合 [1 2 3] を分割する
部分集合を格納するスライスを用意します。最初、部分集合は空集合なので空スライスに初期化します。次に、要素 1 を追加します。部分集合は空スライスなので、手順 1 は適用できません。手順 2 を適用して新しい部分集合 [1] を追加します。
次に要素 2 を追加します。[[1]] に 手順 1 を適用すると、部分集合 [1] に要素を追加して [[1 2]] になります。手順 2 を適用すると、新しい部分集合 [2] を追加して [[1] [2]] になります。最後に 3 を追加します。[[1 2]] に手順 1 を適用すると [[1 2 3]] に、手順 2 を適用すると [[1 2] [3]] になります。[[1] [2]] に手順 1 を適用すると [[1 3] [2]] と [[1] [2 3]] になり、手順 2 を適用すると [[1] [2] [3]] になります。
このように、簡単な方法で集合を分割することができます。実際にプログラムを作る場合、上図を木と考えて、深さ優先で木をたどると簡単です。次のリストを見てください。
リスト : 集合の分割
use strict;
use warnings;
# 集合の表示
sub print_set {
my $xs = shift;
foreach my $ys (@$xs) {
print "[@$ys] ";
}
print "\n";
}
sub part_sub {
my ($ls, $a) = @_;
if (@$ls == 0) {
print_set($a);
} else {
my $x = shift @$ls;
for (my $i = 0; $i < @$a; $i++) {
push @{$a->[$i]}, $x;
part_sub($ls, $a);
pop @{$a->[$i]};
}
push @$a, [$x];
part_sub($ls, $a);
pop @$a;
unshift @$ls, $x;
}
}
sub partition_of_set {
my $ls = shift;
my $x = shift @$ls;
part_sub($ls, [[$x]]);
}
partition_of_set([1, 2, 3]);
partition_of_set([1, 2, 3, 4]);
実際の処理は関数 part_sub で行います。生成した部分集合は累積変数 $a に格納します。$ls が空の場合、追加する要素がなくなったので $a を関数 print_set で表示します。要素がある場合、$ls の先頭要素を shift で取り出して変数 $x にセットします。そして、i 番目の部分集合に $x を追加します。そして、再帰呼び出しから戻ってきたら pop で追加した要素を取り除きます。すべての部分集合に要素を追加したら、$x を要素として持つ部分集合を生成して累積変数 $a に追加します。
リスト : ベル数
use strict;
use warnings;
use bigint;
# 組み合わせの数
sub comb_num {
my ($n, $r) = @_;
if ($n == $r || $r == 0) {
1;
} else {
comb_num($n, $r - 1) * ($n - $r + 1) / $r;
}
}
sub bell_number {
my $n = shift;
my @bs = (1);
for (my $i = 0; $i < $n; $i++) {
my $a = 0;
for (my $j = 0; $j < @bs; $j++) {
$a += comb_num($i, $j) * $bs[$j];
}
push @bs, $a;
}
$bs[-1];
}
for (my $i = 1; $i <= 10; $i++) {
print bell_number($i), "\n";
}
for (my $i = 20; $i <= 50; $i += 10) {
print bell_number($i), "\n";
}
bell_number は公式をそのままプログラムするだけです。累積変数 $bs にベル数を格納します。nＣk は関数 comb_num で求めます。次の for ループで nＣk * B(k) の総和を計算します。あとは、その値を push で bs に追加するだけです。
リスト : 集合のグループ分け
use strict;
use warnings;
# 集合の表示
sub print_set {
my $xs = shift;
foreach my $ys (@$xs) {
print "[@$ys] ";
}
print "\n";
}
sub group_part_sub {
my ($ls, $n, $m, $a) = @_;
if (@$ls == 0) {
print_set($a);
} else {
my $x = shift @$ls;
for (my $i = 0; $i < @$a; $i++) {
if (@{$a->[$i]} < $n) {
push @{$a->[$i]}, $x;
group_part_sub($ls, $n, $m, $a);
pop @{$a->[$i]};
}
}
if (@$a < $m) {
push @$a, [$x];
group_part_sub($ls, $n, $m, $a);
pop @$a;
}
unshift @$ls, $x;
}
}
sub group_partition {
my ($n, $m, $ls) = @_;
my $x = shift @$ls;
group_part_sub($ls, $n, $m, [[$x]]);
}
group_partition(2, 2, [1,2,3,4]);
group_partition(2, 3, [1,2,3,4,5,6]);
group_partition は partition_of_set を改造するだけで簡単に作成することができます。生成する部分集合の大きさを $n に、部分集合の個数を $m に制限するだけです。$i 番目の部分集合に要素を追加する場合、@{$a->[$i]} が $n 未満であることをチェックします。新しい部分集合を追加する場合、@$a が $m 未満であることをチェックします。これで集合をグループに分けることができます。
グループ分けの総数は次の式で求めることができます。
たとえば、n = 3, m = 5 の場合は次のようになります。
これをそのままプログラムすると次のようになります。
リスト : グループ分けの総数
use strict;
use warnings;
use bigint;
# 階乗
sub fact {
my $n = shift;
my $a = 1;
while ($n > 0) {
$a *= $n--;
}
$a;
}
# 組み合わせの数
sub comb_num {
my ($n, $r) = @_;
if ($n == $r || $r == 0) {
1;
} else {
comb_num($n, $r - 1) * ($n - $r + 1) / $r;
}
}
sub group_partition_number {
my ($n, $m) = @_;
my $a = 1;
for (my $k = $n * $m; $k > 0; $k -= $n) {
$a *= comb_num($k, $n);
}
$a / fact($m);
}
print group_partition_number(3, 3), "\n";
print group_partition_number(3, 4), "\n";
print group_partition_number(3, 5), "\n";
階乗は関数 fact で、組み合わせの個数は関数 comb_num で計算します。要素の個数を変数 $k にセットし、comb_num($k, $n) の返り値を累積変数 $a に 乗算します。あとは $k から $n を減算し、$k が 0 でなければ処理を繰り返すだけです。最後に $a / fact($m) を計算して返します。