ある記号列の列挙 #6

enumerate0における履歴は変更不可な文字列として関数の呼出しごとに生成していた。
それぞれの呼出し環境で独立したオブジェクトというのはわたし好みではあるが、
少々お大尽的プログラムでもある。
というのも、渡された履歴の末尾に情報を追加して次へ渡す形なので、
呼んだ側と呼ばれた側の履歴の間に共通部分が多く、もっとまとめられる余地がある。

en6.c

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

static void enumerate0(char *h, unsigned int a, unsigned int b)
{
    if (a == 0 && b == 0) {
        puts(h);
    } else {
        size_t hl = strlen(h);
        if (a > 0) {
            h[hl] = 'a', h[hl + 1] = '\0';
            enumerate0(h, a - 1, b);
            h[hl] = '\0';
        }
        if (b > 0) {
            h[hl] = 'b', h[hl + 1] = '\0';
            enumerate0(h, a, b - 1);
            h[hl] = '\0';
        }
    }
}

static void enumerate(unsigned int a, unsigned int b)
{
    char *h = malloc(a + b + 1);
    h[0] = '\0';
    enumerate0(h, a, b);
    free(h);
}

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

またまたmallocの戻り値をチェックしていない非行プログラムであることに注意。
履歴の最大長はenumerateに与えた二つの記号数の和から求められるので、
enumerateにおいて履歴用の領域を確保する。
enumerate0ではその領域に格納された履歴の末尾に情報を追加して呼び出しを行い、
呼び出しから帰ってきたら追加した情報を削除する。
これで各呼び出しごとに確保していた履歴用領域をひとつの領域にまとめられる。

$ ./en6
aab
aba
baa

enumerate(5, 4)についてen5.cの結果と比較してみる。

$ ./en5 > en5.txt
$ ./en6 > en6.txt
$ diff en5.txt en6.txt
$ wc en6.txt 
 126  126 1260 en6.txt