再帰による場合の数

以前、「多重ループによる場合の数」において、場合の数を入門的なプログラムで表現する場合のコツを書いた。これはプログラムによる問題解決の基本中の基本なのだが、なかなか授業でも真面目に取り上げられることがないので、あえてブログで紹介したものだ。
しかし、その際紹介した書き方は一般性がなかった。つまり、数え上げたい場合の数に応じてプログラムを変更しなければならなかった。記事では、あくまで初心者が理解しやすいことを目指したので、そのような制約があった。今回は、もう少しプログラミングスキルを持った中級者に向けて汎用的に使えるプログラムpermを紹介しよう。
permはr個(0..r-1)からc個とる順列・組合せをすべて表現できる。
void perm(int r, int c, boolean dup, boolean comb) {
permrec(r, c, new int[r], 0, dup, comb);
}
なお、Cではbooleanの代わりにint true=1, false=0を使う。ここで、combは組合せを示す真理値である。組合せのときtrue、順列のときfalseを指定する。dupは重複を許すかどうかを示す真理値である。重複順列または重複組合せのときtrueにする。
permは補助関数としてpermrecを使う。このpermrecは再帰関数である。再帰関数は多重ループより記述能力が高い。再帰を使えば任意の多重ループを表現できる。
void permrec(int r, int c, int[] a, int n, boolean dup, boolean comb) {
if (c == n) {
found(a, c);
return;
}
for (int i = ((comb && n > 0) ? a[n-1] : 0); i<r; i++) {
if (! dup && is_duplicated(a, n, i)) continue;
a[n] = i;
permrec(r, c, a, n+1, dup, comb);
}
}
ここで、dupとcombの使い方に注意してほしい。これらが順列の差を生んでいる。
permrecは補助関数としてis_duplicatedを使う。
boolean is_duplicated(int[] a, int n, int e) {
for (int i=0; i<n; i++) if (a[i] == e) return true;
return false;
}
permrecは数え上げるべき場合を発見したときfoundを呼び出す。foundの本文は解きたい問題に依存する。多くの場合、単純に表示すればよい。また、この例では0..r-1の順列しか生成しない。それ以外の値を使う時にはfoundで写像する。