均等分割とは、１から N2 までの連続した数字を N 個の数字の和が等しい N 個のグループに分けることをいいます。N が 3 の場合を例にすると、１から 9 までの数字を３つのグループに分けて、 それぞれのグループ内の数字の和が 15 になるようにすることです。３つの数字の和が 15 になる組み合わせは、次のようになります。
(1, 5, 9) (1, 6, 8) (2, 4, 9) (2, 5, 8) (2, 6, 7) (3, 4, 8) (3, 5, 7) (4, 5, 6)
上記のグループから数字が重複しないような３つのグループの組み合わせは、 次の２通りがあります。
(1, 5, 9) (2, 6, 7) (3, 4, 8) (1, 6, 8) (2, 4, 9) (3, 5, 7)
グループの組み合わせの注意点として、各グループ内の数字は昇順に並んでいることと、 グループの順序はグループの先頭の数字が昇順に並んでいる必要があります。 次のような並び方は、重複解として認められません。
(5, 1, 9) (2, 6, 7) (3, 4, 8) # グループ内の順序が逆 (2, 4, 9) (1, 6, 8) (3, 5, 7) # グループの順序が逆
今回のプログラムでは、主に何通りのグループの組み合わせ数があるのかを出力します。 というのも、N が 3 の場合は２通りのみですべて表示できますが、N が 4 の場合は 392 通り、N が 5 の場合は 3,245,664 通りとあまりにも多すぎます。そのため、サンプル的な少数の表示にとどめています。
1: use strict; 2: my $n = shift() || 3; my $max = $n ** 2; # N を指定。デフォルトは 3 3: my $ave = (1 + $max) * $n / 2; # グループの数字の合計値 4: my @assign = (1, (0) x $max); # 各数字が割り当て済みか否かを管理する配列 5: my (@group, $count); # @group: 生成したグループを格納する配列 6: comb([], 1); 7: 8: sub comb { 9: my @work = @{shift()}; 10: foreach my $i (@_) { # @_ はグループに追加できる数字のリスト 11: if (@work == $n - 2) { # ２つのメンバを追加してグループを完成 12: my $x = $ave - $i - elm_add(@work); 13: next if $assign[$x] or $x <= $i; 14: push @work, $i, $x; 15: $assign[$i]++; $assign[$x]++; 16: push @group, [@work]; 17: } else { # グループに１つのメンバの追加 18: push @work, $i; 19: $assign[$i]++; 20: } 21: if (@group == $n - 1) { # １つのグループ分けの完成 22: ++$count; 23: if ($count <= 5) { 24: print "(", join(', ', @$_), ") " foreach @group; 25: print "(", join(', ', grep { ! $assign[$_] } 1 .. $#assign), ")\n"; 26: } 27: } elsif (@work == $n) { # 新しいグループ作成のための再帰呼び出し 28: comb([], (grep { ! $assign[$_] } 1 .. $#assign)[0]); 29: } else { # グループへのメンバ追加のための再帰呼び出し 30: my @unassign = grep { ! $assign[$_] } $i + 1 .. $#assign; 31: my $j = $n - @work - 1; my $k = $ave - elm_add(@work); 32: my $range_min = $k - elm_add(@unassign[($#unassign - ($j - 1)) .. $#unassign]); 33: my $range_max = 0; 34: foreach my $m (reverse 0 .. ($#unassign - $j)) { 35: my $o = 0; $o += $_ foreach @unassign[$m .. $m + $j]; 36: if ($o <= $k) { 37: $range_max = $unassign[$m]; last; 38: } 39: } 40: comb(\@work, grep { $_ >= $range_min and $_ <= $range_max} @unassign); 41: } 42: if (@work == $n) { # @work, @group, @assign を元に戻す 43: pop @group; 44: $assign[$work[-1]]--; $assign[$work[-2]]--; 45: pop @work; pop @work; 46: } else { 47: $assign[$i]--; 48: pop @work; 49: } 50: } 51: } 52: 53: print "$count 通り\n"; 54: 55: sub elm_add { 56: return $_[0] if @_ == 1; 57: my $i = 0; $i += $_ foreach @_; 58: return $i; 59: }
今回のプログラムは、冒頭の数行と末尾の小さなサブルーチン以外の大部分は comb サブルーチンになっています。この comb サブルーチンを繰り返し呼び出すことによって、 グループへの数字の追加とグループ分けの両方を行っています。comb サブルーチンを説明する前に、 重要な役割を果たす @assign について説明することにします。N が 4 の場合、冒頭で次のような @assign を生成しておきます。
(添字) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 @assign = (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
配列の利用法には、ハッシュのように機能させるやり方があります。 ハッシュのキーが連続した数字である場合に、配列の添字にハッシュのキーの役割を果たさせることができます。@assign では、各数字が割り当て済みであるか否かを管理します。@assign の添字がハッシュのキーに相当する各数字を表し、 要素の値が 0 の場合が未割り当てを意味し、要素の値が１の場合は割り当て済みを意味します。数字 0 は使いませんので、それに対応する添字 0 にダミーの１を割り当てておきます。 未割り当ての数字を抽出するための、配列とハッシュのコードは次のようになります。
@unassign = grep { ! $assign[$_] } 1 .. $#assign;
@unassign = grep { ! $assign{$_} } sort { $a <=> $b } keys %assign;
grep の評価式が括弧の種類が違うだけで、似ていることに気づかされます。 ハッシュではキーの並ぶ順番はユーザから制御することはできませんが、 当然ですが配列の添字は順番に並んでいるので、並べ替える必要がないことが配列の利点になります。
comb サブルーチンは、自分自身の中から自分自身を呼び出す再帰呼び出し型のサブルーチンです。 comb サブルーチンには、２つの引数を渡します。comb の起動時には、配列のリファレンスと１を渡します。
comb([], 1);
sub comb {
my @work = @{shift()};
foreach my $i (@_) {
...
最初の引数は、現在のグループの割り当て済みのメンバーの数字です。 起動時には何も割り当てられていないので、空のリストを渡します。 渡されたリストは、サブルーチンの最初でグループのメンバーの数字を保持する配列 @work に格納しておきます。現在処理しているグループはサブルーチンによって異なることがあるため、@work はサブルーチン毎に別のローカル変数にしてあります。 ２つ目からの引数は、現在のグループに次に追加することのできる数字のリストです。 起動時には、１つ目のグループの１つ目の数字は１に決まっているため、１のみを渡します。
グループの最初の数字は未割り当ての最小の数字で１つのみですが、 グループの２つ目以降の数字は複数になります。ここで、N が 4 の場合 (１から 16 までで、グループの合計値は 34) を見てみることにしましょう。N が 4 の場合、最初のグループには次のような種類があります。
(1, 2, 15, 16) (1, 3, 14, 16) (1, 4, 13, 16) (1, 4, 14, 15) (1, 5, 12, 16) (1, 5, 13, 15) (1, 6, 11, 16) (1, 6, 12, 15) (1, 6, 13, 14) (1, 7, 10, 16) (1, 7, 11, 15) (1, 7, 12, 14) (1, 8, 9, 16) (1, 8, 10, 15) (1, 8, 11, 14) (1, 8, 12, 13) (1, 9, 10, 14) (1, 9, 11, 13) (1, 10, 11, 12)
最初のグループに１を割り当てた後に、グループに２つ目の数字を割り当てるために comb の再帰呼び出しをします。その際の引数は ([1], 2, 3, 4, 5, 6, 7, 8, 9, 10) になり、[1] の中の１は @work に代入され、残りの数字が foreach のリストになります。foreach のリストの数字は、 グループに追加されるとともに割り当て済みのフラグが立てられます。また、グループが完成したら、@group に追加します。そして、中間の再帰呼び出し間連の処理が終わったら元に戻します。 簡単に分かりやすく書くと、次のようになります。
foreach my $i (@_) {
push @work, $i;
$assign[$i]++;
push @group, [@work] if @work == $n;
# 再帰関連の処理
pop @group if $work == $n;
$assign[$i]--;
pop @work;
}
グループの３つ目以降の数字も同じように割り当てますが、 実際のコードではグループの最後の１つ数字は計算で割り出すようにしています。(1, 2, 15, 16) のグループを生成する場合、最後の 16 は「グループの合計値 - (1 + 2 + 15)」で計算できます。 上のコードをそのまま実行すると、N が 5 の場合に 497 秒かかるのに対して、実際のコードでは 370 秒で実行することができます。
再帰関連の処理は、if 〜 elsif 〜 else を使って３つに分岐します。
if (@group == $n - 1) # １つのグループ分けの終了
再帰呼び出しのサブルーチンでは、再帰呼び出しを停止するための条件を設けるのが必須です。
１つのグループ分けが終了した時点で、再帰呼び出しは停止します。グループは N 個に分割する必要があるのですが、
実質的には N - 1 個のグループに分割した時点でグループ分けは終了しています。@assign
配列の未割り当ての数字を抽出すると、最後のグループができるからです。下の例では、[7, 8, 9, 10]
が最後のグループになります。
@group: ([1, 2, 15, 16], [3, 4, 13, 14], [5, 6, 11, 12])
@assign: 添字 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
(1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1)elsif (@work == $n) # 新しいグループを生成するための再帰呼び出し
新しいグループを作成するための再帰呼び出しは、最初に comb を呼び出したときとほぼ同じです。
引数として空の配列リファレンス [] と、次のグループの最初の数字になる、
その時点での未割り当ての最小の数字１つを渡します。
else # 現在のグループへの次の数字を追加するための再帰呼び出し
現在のグループへの次の数字を追加するための再帰呼び出しの引数は、現在のグループの数字を格納した配列 @work
のリファレンスと、次の数字として追加できる数字のリストを渡します。
次の例は、１つ目のグループの生成が終わっていて、２つ目のグループに１つの数字が割り当てられた状態です。
@group: ([1, 6, 12, 15])
@work : (2)
@assign: 添字 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
(1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0)
@unassign: (3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 16)
@unassign は、@assign から未割り当ての数字を抜き出した配列です。この @unassign を使って、次に追加できる数字の最小値と最大値を求めます。最小値は、残りの数字に @unassign から大きなものを割り当てることで算出できます。具体的には、$ave - (2 + 14 + 16) の計算式で求めることができ、答えは 2 です。
最大値は、残りの数字にそれ自身よりも大きくかつ小さなものを割り当てることで計算できます。 少し分かりにくい表現なので、例を使って説明しましょう。２番目の数字に 10 を割り当てた場合、３、４番目の数字に 11 と 13 を割り当てたとしても 2 + 10 + 11 + 13 = 36 となって合計値を超えるのでダメということになります。 一方 9 を割り当てた場合は 2 + 9 + 10 + 11 = 32 となり合計値を超えないので、この 9 が最大値ということになります。
再帰呼び出しの２番目以降の引数は、@unassign の中から最小値から最大値までの数字を抜き出して渡します。この例では、次のような文になります。
comb(\@work, 3, 4, 5, 7, 8, 9);
以下は、私のパソコン (PentiumM 1.8GHz) でプログラムを実行した結果です。N が 4 まではグループ分けの数もそれほど多くなく時間もほとんどかかりませんが、N が 5 になるとグループ分けの数が 3,245,664 と急に多くなり、時間もかかるようになります。N が 6 の場合も試してみたのですが、 30 日強実行してみてみたのですが終わらないため途中で中止しました。 詳しくは後述しますが、無理な試みだったようです。
N 通り 時間(秒) ------------------------------------------ 2 1 - 3 2 - 4 392 - 5 3,245,664 370 6 20,311,000,000 2,636,400 (未完了)
前節のプログラムでは、最初のグループの先頭の数字から始めて順番に数字を割り当てていました。 グループの合計値になるように１つ目のグループに割り当てが終わると、 次のグループの最初からまた数字を割り当ててというように、 再帰呼び出しが連鎖していきます。N が大きくなると、かなり深い再帰呼び出しになってしまいます。 そこで、別のアプローチを考えてみました。最初にグループを作って、それを組み合わせる方法です。 まずは第１段階として、数の分割プログラムを作ってみました。
この数の分割では、グループの合計値をグループのメンバ数に分割して、 すべての組み合わせを生成します。数の分割のアルゴリズムは、再帰呼び出し型のサブルーチンに適しています。 被分割数 (グループの合計値) と分割数 (グループのメンバ数) を指定してサブルーチンを起動すると、 起動されたサブルーチンの中では被分割数から割り当てた数字を引き、 分割数を１減らして再帰呼び出すことができます。
1: use strict; 2: my $n = shift() || 4; my $max = $n ** 2; 3: my $ave = ($max + 1) * $n / 2; 4: my (%added, %group); 5: 6: foreach my $key1 (1 .. $max) { 7: foreach my $key2 (1 .. $n) { 8: last if $key1 + $key2 - 1 > $max; 9: my $i; $i += $_ foreach $key1 .. ($key1 + $key2 - 1); 10: $added{$key1}->{$key2} = $i; 11: } 12: } 13: 14: divide($ave , 1, $n, ()); 15: 16: sub divide { 17: my ($num, $min, $div, @comb) = @_; 18: my $range_min = $num - $added{$max - $div + 2}->{$div - 1}; 19: $range_min = $min if $range_min < $min; 20: my $range_max; 21: foreach my $i (reverse $range_min .. ($max - $div + 1)) { 22: if ($num >= $added{$i}->{$div}) { 23: $range_max = $i; last; 24: } 25: } 26: foreach my $i ($range_min .. $range_max) { 27: push @comb, $i; 28: if ($div == 2) { 29: push @{$group{$comb[0]}}, join(':', @comb, $num - $i); 30: } else { 31: divide($num - $i, $i + 1, $div - 1, @comb); 32: } 33: pop @comb; 34: } 35: } 36: 37: foreach my $key (sort { $a <=> $b } keys %group) { 38: print "$key => ", scalar(@{$group{$key}}), "\n"; 39: }
%added = ( 1 => { 1 => 1, 2 => 3, 3 => 6, 4 => 10 },
2 => { 1 => 2, 2 => 5, 3 => 9, 4 => 14 },
・・・
13 => { 1 => 13, 2 => 27, 3 => 42, 4 => 58 },
14 => { 1 => 14, 2 => 29, 3 => 45 },
15 => { 1 => 15, 2 => 31 },
16 => { 1 => 16 });計算上の最小値は別に、サブルーチンの引数には次に割り当てる数字の最小値が含まれます。 この引数の最小値は、直前に割り当てた数字に１プラスしたものになっています。 最初の呼び出しでは何も割り当てられていないので、引数の最小値は１になります。19 行目では、計算上の最小値と引数の最小値を比較し、大きい方を最小値として設定します。 最初の呼び出しの最小値は、計算上の最小値が -11 で引数の最小値が１ですので、 結果的に引数の最小値の１が最小値として設定されます。
数の分割プログラムに 4 の引数を与えて実行すると、次の 86 種類のグループが作成されます。N が 4 の場合はグループの合計値は 34 であり、それを 4 個に分割されます。生成された各グループは、%group ハッシュに格納されます。%group のキーはグループの先頭の数字であり、各グループは値の無名配列の中に格納します。
%group = (
1 => ['1:2:15:16', '1:3:14:16', '1:4:13:16', '1:4:14:15', '1:5:12:16', '1:5:13:15', '1:6:11:16', '1:6:12:15',
'1:6:13:14', '1:7:10:16', '1:7:11:15', '1:7:12:14', '1:8:9:16', '1:8:10:15', '1:8:11:14', '1:8:12:13',
'1:9:10:14', '1:9:11:13', '1:10:11:12'],
2 => ['2:3:13:16', '2:3:14:15', '2:4:12:16', '2:4:13:15', '2:5:11:16', '2:5:12:15', '2:5:13:14', '2:6:10:16',
'2:6:11:15', '2:6:12:14', '2:7:9:16', '2:7:10:15', '2:7:11:14', '2:7:12:13', '2:8:9:15', '2:8:10:14',
'2:8:11:13', '2:9:10:13', '2:9:11:12'],
3 => ['3:4:11:16', '3:4:12:15', '3:4:13:14', '3:5:10:16', '3:5:11:15', '3:5:12:14', '3:6:9:16', '3:6:10:15',
'3:6:11:14', '3:6:12:13', '3:7:8:16', '3:7:9:15', '3:7:10:14', '3:7:11:13', '3:8:9:14', '3:8:10:13',
'3:8:11:12', '3:9:10:12'],
4 => ['4:5:9:16', '4:5:10:15', '4:5:11:14', '4:5:12:13', '4:6:8:16', '4:6:9:15', '4:6:10:14', '4:6:11:13',
'4:7:8:15', '4:7:9:14', '4:7:10:13', '4:7:11:12', '4:8:9:13', '4:8:10:12', '4:9:10:11'],
5 => ['5:6:7:16', '5:6:8:15', '5:6:9:14', '5:6:10:13', '5:6:11:12', '5:7:8:14', '5:7:9:13', '5:7:10:12',
'5:8:9:12', '5:8:10:11'],
6 => ['6:7:8:13', '6:7:9:12', '6:7:10:11', '6:8:9:11'],
7 => ['7:8:9:10']);
以下は、N が 3 から 7 までで数の分割プログラムを実行した結果です。 表の各項目は左から、グループの合計値、要した時間 (秒)、グループの総数、 次からの数字の項目はグループの先頭数字でのグループの数になります。 この実行結果を見ると、グループの作成のみであればそれほど時間がかからないことが分かります。N に 6 を指定して前節の均等分割を実行すると 30 日以上かかっても終わりませんでしたが、 グループを作成するだけなら約１秒で終了します。
| N | 合計値 | 時間 | 総数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 3 | 15 | - | 8 | 2 | 3 | 2 | 1 | - | - | - | - | - | - | - | - | - | - | - | - |
| 4 | 34 | - | 86 | 19 | 19 | 18 | 15 | 10 | 4 | 1 | - | - | - | - | - | - | - | - | - |
| 5 | 65 | - | 1,394 | 244 | 238 | 228 | 204 | 174 | 132 | 92 | 52 | 23 | 6 | 1 | - | - | - | - | - |
| 6 | 111 | 1 | 32,134 | 4,739 | 4,555 | 4,291 | 3,942 | 3,521 | 3,037 | 2,514 | 1,974 | 1,453 | 985 | 603 | 321 | 141 | 47 | 10 | 1 |
| 7 | 175 | 9 | 957,332 | 122,389 | 116,471 | 109,439 | 101,478 | 92,578 | 83,012 | 72,883 | 62,546 | 52,215 | 42,295 | 33,009 | 24,715 | 17,569 | 11,771 | 7317 | 4,170 |
| 続き: 17 => 2,112 18 => 927 19 => 331 20 => 90 21 => 14 22 => 1 | |||||||||||||||||||
| 8 | 260 | 315 | 35,154,330 | 3,973,343 | 以下省略 | ||||||||||||||
前節で作成した数の分割プログラムを利用して、最初の節とは異なる均等分割のプログラムを 作成してみましょう。数の分割プログラムですべてのグループが作成されていますので、 残る作業は数字の重複のない N 個の組み合わせを見つけることです。
%group ハッシュは、グループの先頭の数字をキーとしています。１つ目のグループは、%group のキー１に格納されている先頭の数字が１のグループのいずれかになります。 ２つ目のグループは、１つ目のグループに含まれない最初の数字を含むグループが対象になります。 例えば、１つ目のグループとして '1:2:15:16' を選択した場合、含まれない最初の数字は 3 になるので %group のキー 3 に格納されているグループが対象になります。 そのうち、２つ目以降の数字が１つ目のグループと重複しないグループが選ばれて２つ目のグループになります。 ３つ目以降のグループも同じような方法で選ばれて、N 個の組み合わせを見つけることになります。
1: use strict; 2: my (%group, %added, $count); 3: my $n = shift() || 4; my $max = $n ** 2 - 1; 4: my $ave = $max * $n / 2; 5: foreach my $key1 (1 .. $max) { 6: foreach my $key2 (1 .. $n - 1) { 7: last if $key1 + $key2 - 1 > $max; 8: my $i; $i += $_ foreach $key1 .. ($key1 + $key2 - 1); 9 $added{$key1}->{$key2} = $i; 10: } 11: } 12: 13: divide($ave, 0, $n, ()); 14: 15: sub divide { 16: my ($num, $min, $div, @comb) = @_; 17: my $range_min = $num - $added{$max - $div + 2}->{$div - 1}; 18: $range_min = $min if $range_min < $min; 19: my $range_max; 20: foreach my $i (reverse $range_min .. ($max - $div + 1)) { 21: if ($num >= $added{$i}->{$div}) { 22: $range_max = $i; last; 23: } 24: } 25: foreach my $i ($range_min .. $range_max) { 26: push @comb, $i; 27: if ($div == 2) { 28: my $bit = '0' x ($max + 1); 29: substr($bit, $_, 1, 1) foreach @comb, $num - $i; 30: push @{$group{$comb[0]}}, $bit; 31: } else { 32: divide($num - $i, $i + 1, $div - 1, @comb); 33: } 34: pop @comb; 35: } 36: } 37: 38: check($_) foreach @{$group{0}}; 39: 40: sub check { 41: my $pattern = shift; 42: my $key = index $pattern, '0'; # 未割り当ての最初の数字を取得する 43: foreach my $item (@{$group{$key}}) { 44: my $chk = "$pattern" & "$item"; 45: next if $chk =~ /1/; # 数字が重複する場合はスキップする 46: my $work = $pattern; 47: $work = "$work" | "$item"; # グループの合成 48: ($work =~ tr/0// == $n) ? $count++ : check($work); 49: } 50: } 51: 52: print "$count 通り\n";
この節のプログラムでは、前節の数の分割プログラムを少し変更しています。均等分割は１から N2 までの数字を扱いますが、これを 0 から (N2 - 1) までの数字に変更しています。 コンピュータで数を扱うには、0 から数を数えたほうが便利な場合があります。この場合も、それに該当します。 元に戻すには、各数字にプラス１するだけで済みます。
もう１つの変更した点は、%group へのグループデータの格納形式です。 前節では数字をコロンで結んで '1:2:15:16' のようにしていましたが、この節では '0:1:14:15' の代わりに '1100000000000011' のようにしています。0 と１からなる文字列の長さは N の２乗分あり、各位置が各数字を示し、その値の１のものが割り当て済みであることを示します。 0 と１の文字列に変更したのは、数字の重複のチェックを考えてのことです。
Perl の論理演算は、文字列同士に対しても使うことができます。 文字列同士の論理演算では、２つの文字列の同じ位置の文字間でビット演算を行います。まずは、'0' と '1' との１文字同士の論理演算を考えてみます。次は、'0' と '1' の文字コードです。
'0' 0011 0000 '1' 0011 0001
'0' と '1' の文字コードを見ると、論理和 (|) と論理積 (&) はビットの論理演算と同じ結果になることが分かります。ただし、排他的論理和は、使うことができません。0 と１の文字列に変換したグループ同士では、数字の重複のチェックやグループの合成を簡単に行うことができます。 以下の左側が数字の重複がある例で、右側が数字の重複がない例です。
'0:1:14:15' '1100000000000011' '0:1:14:15' '1100000000000011'
'2:3:10:15' '0011000000100001' '2:3:12:13' '0011000000001100'
-------------------------- ----------------------
& '0000000000000001' '0000000000000000'
| '1111000000001111'
数字の重複をチェックするには、文字列同士の論理積を使います。 数字が重複していると論理積の結果は文字列中に１が残り、重複していない場合は文字列がすべて 0 の並びになります。上の例は１つ目のグループと２つ目のグループの組み合わせを試しているところですが、 左側の例は１が残るのでスキップし、右側の例はすべて 0 になるので次に進むことができます。 数字の重複がないことが確認できたら、グループの合成を行います。 グループの合成には、文字列同士の論理和を使用します。右側の例のように、それまでに割り当てられた数字が 1 になります。
check サブルーチンは、簡単な構造になっています。check サブルーチンは、均等分割の最初のグループがすべて格納されている配列 @{$group{0}} の１つ１つを引数にして呼び出します。呼び出されたサブルーチンでは、受け取った 0 と１からなる文字列の引数から未割り当ての最初の数字を割り出して、その数字をキーにして %group から次の組み合わせのためのグループを foreach のリストに指定します。foreach のリストのそれぞれは、上で説明した論理演算で数字の重複をテストします。 数字の重複をテストして通過したものは、グループの組み合わせが終了したものはカウントし、 途中のものは再帰呼び出しをします。
この節の均等分割(2)のプログラムを実行すると、N が 5 の場合に 155 秒かかりました。最初の節のプログラムが 370 秒かかりましたので、半分以下にはなったのですが N を 6 にして実行するにはまだまだ遠いようです。N が 6 では６つのグループを組み合わせることになりますが、 １つ目のグループ (１を含むグループ: この節では 0 を含むグループ) だけで 4,739 あります。まずは、4,739 ある１つ目のグループの内の１つだけを実行してみました。
組み合わせ数: 2,549,091,482 ( x 4,739 = 12,080,144,533,198) 時間: 450,274s ( x 4,739 = 2,133,848,486s)
１つだけですが、組み合わせ数が 25.5 億強、時間が５日と５時間強となってしまいました。 カッコ内の数字は単に 4,739 を掛けただけで、(１つ目のグループ毎に組み合わせ数が違うので) 正確ではありませんが１つの目安です。計算結果では 67 年以上かかることになるので、 パソコンで実行するには無理というのが結論になってしまいました。
(2011/09/01)