ある記号列の列挙 #3

enumerate(5, 4)では詳細に立ち入るにはちょっと大きい。
そこでスケールダウンしてenumerate(2, 1)について見てみる。
実はenumerate(2, 1)についてのグラフは既に出ている。
前回の記事の最後に出したグラフの中で、
ノードenumerate(2, 1)を根にして辿ることのできるノード6個エッジ7本から成るサブグラフが、
enumerate(2, 1)から始まる呼び出しシーケンスに対応している。
en2.cにおいてenumerate(5, 4)からenumerate(2, 1)への変更のみ行い、

en3.c

...snip
int main(void)
{
    puts("digraph {");
    enumerate(2, 1);
    puts("}");
    return 0;
}

実行すると、

$ ./en3 | dot -Tpng -o en3.png

tredを使って多重エッジをまとめていないのでエッジは8本あるが、
前出のグラフのenumerate(2, 1)をルートとするサブグラフであることが分かる。
呼び出しは(2, 1)から(1, 1), (0, 1), (0, 0)と至り、
(0, 1), (1, 1)と戻って(1, 0), (0, 0)へ進み、
(1, 0), (1, 1), (2, 1)まで戻って(2, 0), (1, 0), (0, 0)に進む。
最後に(1, 0), (2, 0), (2, 1)と戻ってmainに返ってくる。
呼び出し順序はおいておき、単に有向グラフとしてみたとき、
(2, 1)から(0, 0)へ至るルートは3ルートある。
そのとき通るエッジのラベルに注目すると、

aab
aba
baa

の三通りの記号列が得られる。
これがある記号二個と別の記号一個からなる記号列の列挙となっている。