今回は、下記の小町算を解くプログラム取り上げます。小町数とは１から 9 までのすべての数から構成される数をいい、小町算とはすべての数から構成される計算式をいいます。 下記の計算式の A から I は、すべて異なる数字を意味しています。
AB EF -- + -- = I CD GH
use strict;
my (@work, @result);
comb(grep { ! /0/ and ! /(.)\1/ } 12 .. 98);
sub comb {
my @num = @_;
foreach my $i (0 .. ($#num - (3 - @work)) {
push @work, $num[$i];
if (@work == 4) {
my $rest = 45 - eval(join '+', map { split // } @work);
foreach ("123", "132", "213", "231", "312", "321") {
my ($j, $k, $l) = split //;
push @result, [$work[0], $work[$j], $work[$k], $work[$l], $rest]
if $work[0] * $work[$l] + $work[$k] * $work[$j] == $rest * $work[$j] * $work[$l];
push @result, [$work[$j], $work[0], $work[$k], $work[$l], $rest]
if $work[$j] * $work[$l] + $work[$k] * $work[0] == $rest * $work[0] * $work[$l];
}
} else {
my ($j, $k) = split //, $num[$i];
comb(grep { ! /$j/ and ! /$k/ } @num[($i + 1) .. $#num]);
}
pop @work;
}
}
print "$$_[0]/$$_[1] + $$_[2]/$$_[3] = $$_[4]\n" foreach sort { $a->[4] <=> $b->[4] } @result;
プログラムの冒頭で、使用する配列 @work と @result を宣言しています。@work は作業用の配列で、２桁の数字４つを格納するのに使います。@result は解を格納しておくための配列で、 プログラムの最後で解をまとめて出力するために使います。
計算式 AB/CD + EF/GH = I には、２桁の数字４つと１桁の数字１つが使われています。 ２桁の数字は、0 が含まれていないことと、数字が重複しない (別の数字の組み合わせである) ことが必要です。 この条件を満たす２桁の数字のすべてのリストは、次の文で得ることができます。
grep { ! /0/ and ! /(.)\1/ } 12 .. 98;
次に、上のリストから４つの２桁の数字が別の数字からなる組み合わせを生成します。 このコードを説明する前に、基本となるリストや配列から組み合わせを生成する方法を考えてみましょう。
use strict;
my @work; my $n = 4;
comb(1 .. 10);
sub comb {
my @list = @_;
foreach my $i (0 .. ($#list - ($n - 1 - @work))) {
push @work, $list[$i];
if (@work == $n) {
# ここで何らかの処理を行う
} else {
comb(@list[($i + 1) .. $#list]);
}
pop @work;
}
}
(foreach のリスト 0 .. ($#list - ($n - 1 - @work)) は、単に 0 .. $#list
と書いても多少無駄なループが発生するだけで実行上は問題ありません。)
ここで、組み合わせの実例を挙げてみましょう。 競馬の馬券には、馬連・馬単・３連複・３連単などがあります。馬単と３連単は順列ですが、 馬連と３連複は組み合わせです。次のプログラムは、7 頭立ての３連複の馬券の種類を出力します。
use strict;
my (@work, $result);
comb(1 .. 7);
sub comb {
my @list = @_;
foreach my $i (0 .. $#list) {
push @work, $list[$i];
if (@work == 3) {
$result .= sprintf("%-10s", join(',', @work));
$resule =~ /(.*)$/;
$result =~ s/\s*$/\n/ if length($1) > 60;
} else {
comb(@list[($i + 1) .. $#list]);
}
pop @work;
}
}
print "$result\n";
1,2,3 1,2,4 1,2,5 1,2,6 1,2,7 1,3,4 1,3,5 1,3,6 1,3,7 1,4,5 1,4,6 1,4,7 1,5,6 1,5,7 1,6,7 2,3,4 2,3,5 2,3,6 2,3,7 2,4,5 2,4,6 2,4,7 2,5,6 2,5,7 2,6,7 3,4,5 3,4,6 3,4,7 3,5,6 3,5,7 3,6,7 4,5,6 4,5,7 4,6,7 5,6,7
わずか 7 頭ですが、35 (7 x 6 x 5 ÷ 3!) 通りの組み合わせがあります。これが 15 頭になると 445 (15 x 14 x 13 ÷ 3!) 通り、18 頭では 816 (18 x 17 x 16 ÷ 3!) 通りの組み合わせになってしまいます。確率的に当てるのは大変ですね。先ほど、３連単は順列である述べました。 ３連単の場合は３連複の６倍 (÷ 3! が不要) の種類があることになり、当てるのはさらに難しくなります。 ３連単は、上のプログラムを少し修正することで生成することができます。 再帰呼び出しの引数を少し工夫するだけです。組み合わせでは現在選択されている要素の次の要素から残り要素 (comb(@list[($i + 1) .. $#list]);) を渡すのに対して、 順列では現在選択されている要素を除外した要素 (perm(@list[0 .. ($i -1), ($i + 1) .. $#list]);) を渡すことが必要です。
今回の計算式でも、同様の方法で組み合わせを生成します。 違うのは、再帰呼び出しの際に渡す引数の部分です。 通常の組み合わせでは現在選択されている要素の次からすべて渡しますが、 今回の組み合わせでは残りの要素から現在の選択されている要素に含まれている数字を含むものを除外します。
my ($j, $k) = split //, $num[$i];
comb(grep { ! /$j/ and ! /$k/ } @num[($i + 1) .. $#num]);
再帰呼び出しを繰り返すことで、@work には数字に重複がない４つの２桁の数字が収集されます。 ４つの数字が収集されたら、計算式に当てはめて検証することになります。計算式は AB/CD + EF/GH = I ですが、コードでは整数演算ができるように計算式を AB x GH + EF x CD = I x CD x GH 変更して行います。この計算をするために、残りの数字を先に求めておきます。残りの数字は、１から 9 までの和から使用されている８個の数字の和を引くことで求めます。
my $rest = 45 - eval(join '+', map { split // } @work);
これで異なる数字からなる２桁の数字４つと１桁の数字１つが揃ったので、 いよいよ計算式に当てはめていきます。１桁の数字は I に割り当てられるのが決まっていますが、@work のそれぞれの２桁の数字は AB, CD, EF, GH のどこに割り当てるかは決まっていません。 そこで、割り当てを試していくため、foreach ループを使って調べていきます。
foreach ("123", "132", "213", "231", "312", "321") {
my ($j, $k, $l) = split //;
push @result, [$work[0], $work[$j], $work[$k], $work[$l], $rest]
if $work[0] * $work[$l] + $work[$k] * $work[$j] == $rest * $work[$j] * $work[$l];
push @result, [$work[$j], $work[0], $work[$k], $work[$l], $rest]
if $work[$j] * $work[$l] + $work[$k] * $work[0] == $rest * $work[0] * $work[$l];
}
foreach ループですべての割り当てをしてしまうと、AB/CD + EF/GH = I と EF/GH + AB/CD = I の２つの計算式を試すことになってしまいます。正解がある場合は、重複解が発生します。 この重複解を防止するために、$work[0] は AB または CD のみに割り当てています。
プログラムの最後で、@result に収集しておいた解を I の値が小さい順から出力します。
29/87 + 36/54 = 1 29/16 + 57/48 = 3 75/41 + 96/82 = 3 91/42 + 65/78 = 3 75/31 + 98/62 = 4 15/69 + 87/23 = 4 78/21 + 63/49 = 5 64/18 + 39/27 = 5 72/19 + 46/38 = 5 57/13 + 94/26 = 8 75/13 + 84/26 = 9
(2007/11/15)