ある記号列の列挙 #7
この問題では特にコストが高いわけではないと思うが、
呼び出すたびにstrlen
で履歴文字列の長さを求めるのはちょっとという向きには、
新たに履歴に文字を追加する時の場所を履歴とともに渡すことでstrlen
を消せる。
en7.c
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct { char *h; size_t tail; } hist_t; static void enumerate0(hist_t *h, unsigned int a, unsigned int b) { if (a == 0 && b == 0) { puts(h->h); } else { char *hh = &(h->h[h->tail]); if (a > 0) { hh[0] = 'a', hh[1] = '\0'; h->tail++; enumerate0(h, a - 1, b); hh[0] = '\0'; h->tail--; } if (b > 0) { hh[0] = 'b', hh[1] = '\0'; h->tail++; enumerate0(h, a, b - 1); hh[0] = '\0'; h->tail--; } } } static void enumerate(unsigned int a, unsigned int b) { hist_t h; h.h = malloc(a + b + 1); h.tail = 0; h.h[h.tail] = '\0'; enumerate0(&h, a, b); free(h.h); } int main(void) { enumerate(2, 1); return 0; }
第一引数が環境に関わるものという意味的インタフェイスを変えないようにするために、
履歴文字列とその末尾を指すインデックスとをひとまとめにしている。
末尾に付け加えたり末尾の文字を削除したりするのは前と同じで、
それに合わせてインデックスの増減を行う処理が増えているだけである。
書いておいてなんだがこのコードでここまでやるほどでもないとは思う。