ある記号列の列挙 #4

したがってこの列挙をプログラムにさせるには、
ルートノード(2, 1)から葉ノード(0, 0)まで辿ってきたエッジのラベルを順に表示すればいい。
とはいえ単純に考えすぎて、

en4.c

#include <stdio.h>

static void enumerate(unsigned int a, unsigned int b)
{
    if (a == 0 && b == 0) {
        putchar('\n');
    } else {
        if (a > 0) {
            putchar('a');
            enumerate(a - 1, b);
        }
        if (b > 0) {
            putchar('b');
            enumerate(a, b - 1);
        }
    }
}

int main(void)
{
    enumerate(2, 1);
    return 0;
}

エッジを進むたびにそのラベルを出力し、
葉ノードに達したとき(a == 0 && b == 0)に改行を出力して行を完結させる。
元のコードの骨格に葉ノードに到着したときの処理を加えただけである。
葉であるなら残り記号数はともに0であるから、
残り記号数が0か否かを判断する元のコードの部分はelse節に放り込んでしまっている。

$ ./en4
aab
ba
baa

二つ目の記号列が明らかにおかしい。
これは当然の結果で、関数の呼び出し後に返ってくるとき、つまり有向グラフのエッジを逆向きに辿るとき、
ルートノードまでいちいち戻らず、途中で別の順方向のルートがあればそちらに進むからである。
この動作が深さ優先探索のトラバースの仕方である。
問題は単純にエッジを進むたびにそのラベルを出力することにある。
葉に到達したらルートまで戻って別ルートを辿る、という動作であれば、これでも問題ないが、
このコードの骨格はそのような動作を行わない。
解決策としては、ノードごとにそのノードまで順方向に辿ってきたときのエッジラベルの履歴情報を持たせる。
葉ノードに達した時点でその葉ノードの持つ履歴情報はルートノードから辿ってきたエッジ履歴になっており、
この履歴がまさに求めている記号列のひとつであり、葉ノードにてその履歴を表示すればいい。
たとえば、前回の記事に出したグラフでいえば、
(2, 1)は履歴情報として空の記号列を持ち、
(1, 1)はa、(2, 0)はbが履歴となる。
これより先のノードについては(0, 1)はひとつの履歴aaを持つが、
残る二つのノードは辿ってきたルートによって異なる複数の履歴を持つことになる。