ある記号列の列挙 #5

前述の方針に従って実装してみる。

en5.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static char *append_history(const char *h, const char *a)
{
    return strcat(strcpy(malloc(strlen(h) + strlen(a) + 1),  h), a);
}

static void enumerate0(const char *h, unsigned int a, unsigned int b)
{
    if (a == 0 && b == 0) {
        puts(h);
    } else {
        if (a > 0) {
            char *t = append_history(h, "a");
            enumerate0(t, a - 1, b);
            free(t);
        }
        if (b > 0) {
            char *t = append_history(h, "b");
            enumerate0(t, a, b - 1);
            free(t);
        }
    }
}

static void enumerate(unsigned int a, unsigned int b)
{
    enumerate0("", a, b);
}

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

今回、enumerateを呼び出す際にはそれまでの呼び出しの履歴も必要となる。
そこで履歴を引数として与えるようにしたが、
ユーザであるmain関数にすれば履歴の話は実装に関わる問題であり、
それが直接mainから見えることは良いことではない。
また、これまでのインタフェイスが変わることも好ましくないだろう。
そこでenumerateをサポートして再帰しながら実際に仕事をする関数enumerate0を定義する。
enumerate0は文字列で表現された履歴を引数に含むが、その骨格はen4.cのenumerateと同じである。
どちらの記号を選択したかで履歴を作成して再帰呼び出しを行い、葉に到達した時点でその履歴を一行に出力する。
append_historyは自分が受け取った履歴に新たに選択した記号を付け加えた履歴を作成する。
新規に履歴用のメモリをヒープから得るので再帰から帰った時点でそれを解放している。
mallocがメモリ割り当てに失敗したときの処理してないけどまあいいか。
enumerateは履歴として空文字列を設定してenumerate0を呼び出すだけである。

$ ./en5
aab
aba
baa

今度はうまく列挙できた。
ためしにmainのenumerate(2, 1)をenumerate(5, 4)に書き換えてみよう。

$ ./en5
aaaaabbbb
aaaababbb
aaaabbabb
aaaabbbab
aaaabbbba
aaabaabbb
aaabababb
aaababbab
...snip
bbababaaa
bbabbaaaa
bbbaaaaab
bbbaaaaba
bbbaaabaa
bbbaabaaa
bbbabaaaa
bbbbaaaaa
$ ./en5 | wc
    126     126    1260
$ ./en5 | sort | uniq | wc
    126     126    1260

きちんと個の記号列が重複も欠けもなく出力されているようだ。
wcがカウントした文字数1260は9個の記号からなる記号列に改行分を加えた10文字分で行が構成されているからである。