イケてないプログラム（使えない成果物）に見られる３つの共通点

クイックソートの話で書いたとおり、相変わらず Excel - VBA と格闘する日々が続いております・・・orz

「大企業にありがちな問題。委託開発の甘い罠・・・」でも書いたとおり、今まで外注して作ったソフトウェアってほぼ 100% の確率でイケていないものが完成してます。年末に納品されたソフトウェアのできも酷いの何のって・・・

さて、いままで見てきたイケてないプログラムのダメソースに共通して言えることが３点ありまして、

のいずれか、もしくは全部が当てはまります。大抵は全部ですね。こういったソースが納品されると、センス無いなぁ〜と思っちゃうわけ。こういうは案の定、要求する処理時間を大幅に上回っていたりバグが多かったりします・・・。

さて、今回外注したソフトウェアのキモとなる部分の１つとして、データの組合せ問題を解くロジックとソートの問題がありました。ソートについては、「再帰処理のクイックソート vs 非再帰処理のクイックソート」で記述したので、そちらを見て頂くとして、組合せ問題もなかなかにキワモノのコードが書かれていました。

ってか、データの組合せ問題を解くロジックがアホでして、

ってかかれていたのですが、コレではループ処理が発散して１日たっても結果は帰ってきません。

だろ、普通はと思ったりします。あり得ない・・・

さて、順列と組合せは高校で習う数学の問題なので、殆どの方は一度は経験していると思われますが、実際プログラムの中でお目にかかることは少ないと思います。

取りあえず、Perl で実装してみましょう。CPAN には、Algorithm::Permute っていうモジュールがありまして、XS で書かれていて非常高速ですが、今回は頭の体操と言うことで、生 Perl で書いてみることにします。

順列　_nP_m　で得られるデータの組み合わせを求める関数

## nPm = n(n-1)....(n-m+1) を再帰処理で全パターン生成する
sub permute {
	my $m = shift;		## m 個を選択する
	my (@array) = @_;	## @_ から
	&permute_core($#array+1, $m, @array);
}
sub permute_core {
	my $n = shift;	## n 個の要素から
	my $m = shift;	## m 個を選択する
	## m 個選択済みなら再帰処理を終了
	return @_ if(@_ <= $n-$m+1);
	my @result;
	## 要素群 P(x) から要素をどこから取り出すか？ 1 〜 n 個のパターン
	for (my $i = 0; $i < @_; $i++) {
		my @data = @_;
		## 要素群 P(x) から i 個目の要素を１つ取り出す
		my $item = splice(@data, $i, 1);
		## 残った要素群 P(x+1) から次の要素を取り出す処理を再起処理にまかせる
		push(@result, map { "$item,$_" } &permute_core($n, $m, @data));
	}
	## 要素群 P(x) の全組み合わせを返す
	return @result;
}
my @data = (a, b, c, d, e, f);
print join(" / ", &permute(3, @data)), "\n";

組み合わせ　_nC_m　で得られるデータの組み合わせを求める関数

sub combinatorial {
	my $m = shift;		## m 個を選択する
	my (@array) = @_;	## @_ から
	&combinatorial_core($#array+1, $m, @array);
}
sub combinatorial_core {
	my $n = shift;	## n 個の要素から
	my $m = shift;	## m 個を選択する
	## m 個選択済みなら再帰処理を終了
	return @_ if($m==1);
	my @result;
	## 要素群 P(x) から要素をどこから取り出すか？ 1 〜 n 個のパターン
	for (my $i = 0; $i < @_; $i++) {
		my @data = @_;
		## 要素群 P(x) から i 個目の要素を１つ取り出す
		my $item = splice(@data, $i, 1);
		## 使用済みの要素は破棄する
		@data = splice(@data, $i);
		## 残った要素群 P(x+1) から次の要素を取り出す処理を再起処理にまかせる
		push(@result, map { "$item,$_" } &combinatorial_core($#data, $m-1, @data));
	}
	## 要素群 P(x) の全組み合わせを返す
	return @result;
}
my @data = (a, b, c, d, e, f);
print join(" / ", &combinatorial(4, @data)), "\n";

再帰処理のプログラムって慣れないと頭がパニックりますよね。僕自信、高校の数学を公式をかなり忘れてしまっているのを痛感しました。