リストの組み合わせ

今回は、リストの組み合わせを生成するプログラムを取り上げます。１個からリストの要素数 n までの組み合わせをすべて生成します。(a, b, c, d) のリストがあった場合に、次のような組み合わせが生成されます。 (なお、('a', 'b', 'c', 'd') のようにクォートすべきですが、本文中ではクォートを省略しています。)

foreach を積み重ねると、リストの要素の組み合わせを作ることができます。最初の foreach の引数リストには、リストの要素を全部渡します。そして、そのとき選択されている要素を表示します。２番目の foreach の引数リストには、前の foreach で選択されている要素の次から残りを渡します。２番目の foreach では、最初に選択されているものと２番目に選択されたものを合わせて表示します。３番目以降の foreach も同様の処理を続けます。次のプログラムを実行すると、上記とまったく同じ結果が表示されます。

use strict;
my @list = 'a' .. 'd';

foreach my $i (0 .. $#list) {
  print "$list[$i]\n";
  last if $i == $#list;
  foreach my $j ($i + 1 .. $#list) {
    print "$list[$i], $list[$j]\n";
    last if $j == $#list;
    foreach my $k ($j + 1 .. $#list) {
      print "$list[$i], $list[$j], $list[$k]\n";
      last if $k == $#list;
      print "$list[$i], $list[$j], $list[$k], $list[$#list]\n";
    }
  }
}

foreach の引数リストに配列そのものを指定することが多いですが、上のプログラムでは配列の添字を使っています。配列そのものを引数リストにすると、次の要素を指定したり最後の要素を検出するのがやや困難になります。また、foreach の制御変数にデフォルトの $_ を使うと、内側の foreach から外側の foreach の制御変数を見ることができなくなるので個別に指定する必要があります。

foreach 積み重ねのプログラムの欠点は、リストの要素数が変わるとその都度 foreach の積み重ね数を変えなければならない点にあります。例えば @list の要素数を４個から 10 個に変えると、foreach を６段追加しなければなりません。それでは面倒で汎用性に欠けるので、冒頭の @list の数に応じて自動的に組み合わせを生成するプログラムを作ってみました。

次の節からの３つのプログラムは、foreach 積み重ねプログラムの別バージョンです。同じことをするプログラムを３つも思うかもしれませんが、プログラミングの引き出しを増やすという意味でいろいろと考えてみるのは面白いものです。

再帰呼び出しサブルーチンを使う

再帰呼び出しのサブルーチンを使うと、foreach の積み重ねを変換することができます。次のプログラムは、上記のプログラムと行っていることはほぼ同じになります。サブルーチンを呼び出す毎に、foreach が一段追加されることになります。リストの数に応じて foreach が自動的に積み重なるので、comb() の引数を変えるだけで何個のリストにも対応できます。

use strict;
my @work;
comb('a' .. 'd');

sub comb {
  foreach my $i (0 .. $#_) {
    push @work, $_[$i];
    print join(', ', @work), "\n";
    comb(@_[$i + 1 .. $#_]) if $i < $#_;
    pop @work;
  }
}

再帰呼び出しのコードでは foreach の制御変数が同じ名前のため、呼び出し元の制御変数にアクセスすることができません。そのため、その都度選択された要素を保存するための配列 @work を使います。@work の中にすべての組み合わせが生成され、プログラムの終了時には空になります。

再帰呼び出しのコードを利用した例を、１つ取り上げます。次のプログラムは、1 ～ 9 の組み合わせの中から和が 15 になるものを見つけるものです。

use strict;
my @work;
comb(1 .. 9);

sub comb {
  foreach my $i (0 .. $#_) {
    push @work, $_[$i];
    my $sum = eval join '+', @work;
    if ($sum == 15) {
      print "15 = ", join(' + ', @work), "\n";
    } elsif ($sum < 15) {
      comb(@_[$i + 1 .. $#_]) if $i < $#_;
    }
    pop @work;
  }
}

追加してあるのは、その都度組み合わせの和を求めているところです。和が 15 である場合は表示し、和が 15 よりも小さい場合は再帰呼び出しをします。和が 15 よりも大きいか等しい場合は、それ以上の数字の追加は必要ないので再帰呼び出しを打ち切ります。プログラムの実行の結果は、次のようになります。

リストの要素を１つずつ追加する

２つ目のプログラムは、リストの要素を１つずつ追加しながら組み合わせを生成していきます。 n + 1 個の組み合わせは、n 個の生成済みの組み合わせから生成することができます。その方法は n 個の生成済みの組み合わせに、新たに n 個の組み合わせに n + 1 個目の要素を追加したものと n + 1 個目の要素自身を追加します。例えば、２つの要素の組み合わせは (a, ab, b) となります。ここに３つ目の要素 c を追加するには、(a, ab, b) に c を追加した (ac, abc, bc) と c をもとの組み合わせと合わせます。結果は (a, ab, b, ac, abc, bc, c) となり、これが３つの要素の組み合わせとなります。

use strict;
my @comb;

foreach my $char ('a' .. 'd') {
  push @comb, map({ [@$_, $char] } @comb), [$char];
}

print join(', ', @$_), "\n" foreach @comb;

n + 1 個の組み合わせは n 個の組み合わせから生成するため、配列等 (上のコードでは @comb) に格納しておくことが必要です。プログラムの foreach ループが終了すると、生成したすべての組み合わせが @comb に格納されます。また、前節と次節のプログラムではいわゆるソート順に組み合わせが生成されますが、この節のプログラムでは違った順で生成されます。この節のプログラムの実行結果は、次のようになります。

配列の添字を操作する

最後の３つ目のプログラムは、別の配列に元の配列の添字を格納して、要素をインクリメントしながら配列スライスを生成するものです。組み合わせを生成するために配列１つしか使わないので、これまでのプログラムよりも少しのリソースで済みます。

use strict;
my @list = 'a' .. 'd';
my @slice = (-1, (0) x $#list);
my ($i, $tail) = (0, $#list);

while ($tail) {
  $slice[$i]++;
  foreach my $j ($i + 1 .. $#list) {
    if ($slice[$j - 1] < $#list) { $slice[$j] = $slice[$j - 1] + 1; }
    else { $tail = $j - 1; last; }
  }
  foreach my $j ($i .. $tail) {
    print join(', ', @list[@slice[0 .. $j]]), "\n";
  }
  $i = $tail - 1;
}

配列 @list からスライスを切り出すための配列 @slice を用意し、@slice の要素をインクリメントしながら @list[@slice] で組み合わせを生成していきます。@slice の要素数は @list の要素数と同じで、while ループの中でインクリメントします。

インクリメントでは、インクリメントした要素だけでなく、次の要素から $#list になるまで１ずつ増やします。while ループの中での @slice の遷移は、次の表のようになります。太字の要素はインクリメントした要素で、下線の要素が $#list に達した要素です。なお、$i は @slice のインクリメントした要素の添字で、$tail が $#list に達した要素の添字です (@slice が @list の添字を格納した配列なので少しややこしいですが)。

例えば while ループに入る前の (-1, 0, 0, 0) は、while ループの１回目で先頭の -1 を 0 にインクリメントし、その次の要素から１ずつ増やすので (0, 1, 2, 3) になります。この場合、$i に 0 が $tail に 3 が割り当てられます。組み合わせ (配列のスライス) は、@list[0 .. $j] の形で $j が $i から $tail まで繰り返し生成されます。この場合は、上の表の１行目の右側の４つの組み合わせが生成されます。

while ループの中での @slice の要素のインクリメントは、１回目だけ特別で @list の初期添字と同じになるようにします。２回目からは、$#list の値になっている要素 ($tail の指している要素) の１つ前をインクリメントします。このインクリメント繰り返すと、$tail が 0 になり、すべての組み合わせが生成されます。