三輪車の再発明(2)
ひどいヘタレっぷりを露呈ちう＿|￣|○|||
先日のコードで再帰関数だったselect()は、結局次のようにループ化できた*1。
/* f_から始まる増分1の等差数列n項から、昇順にr_項取り出す組み合わせを列挙 */
select()
{
int i, j, k, r, t;
r = 0;
i = f_;
do {
for (; i < f_ + n_; ++i) {
a[r] = i;
if (r + 1 == r_) {
/* 取り出した要素の表示 */
printf("(");
for (j = 0; j < r_; ++j)
printf("%d ", a[j]);
printf("),(");
/* 残った要素の表示 */
t = f_;
a[r_] = f_ + n_;
for (j = 0; j <= r_; ++j) {
for (k = t; k < a[j]; ++k)
printf("%d ", k);
t = a[j] + 1;
}
puts(")");
} else {
i = a[r++];
}
}
i = a[--r] + 1;
} while (r >= 0);
}
f_=5, n_=5の結果。
(5 6 7 ),(8 9 ) (5 6 8 ),(7 9 ) (5 6 9 ),(7 8 ) (5 7 8 ),(6 9 ) (5 7 9 ),(6 8 ) (5 8 9 ),(6 7 ) (6 7 8 ),(5 9 ) (6 7 9 ),(5 8 ) (6 8 9 ),(5 7 ) (7 8 9 ),(5 6 )
最後の while (r >= 0) を while (r > 0) にすると
(5 6 7 ),(8 9 ) (5 6 8 ),(7 9 ) (5 6 9 ),(7 8 ) (5 7 8 ),(6 9 ) (5 7 9 ),(6 8 ) (5 8 9 ),(6 7 )
となって、A面ダイス問題の解の列挙に使える。
君アルゴリズムだけで何日かけてますか？_n。|||
まあ得るところもあって、末尾再帰にならない再帰関数(スタック必須)のループ化の手順を再発見した、、
関数型言語を理屈込みで使えてる人はもっと洗練されたやり方を知ってるに違いない
