冪集合

藤田 博司さんの「て日々」
http://www.tenasaku.com/cgi-bin/tepipi-latest.pl
2011年6月1日(水)より。

n=0,1,2,3,4,5 の場合に R(n) を書き下しなさい.
R(n) というのは,
　　　R(0)=0R(1)={0}R(2)={0,{0}}R(3)={0,{0},{{0}},{0,{0}}}
という具合で, R(0)=0 (空集合) から出発し, R(n+1) としては R(n) の冪集合をとる, という仕方で再帰的に定義される.

Maximaで書きました。

mysubset(bits_pattern, s) := block([result : {}, n : length(s), slist : listify(s)],
  for i : 1 thru n do
    if mod(quotient(bits_pattern, 2^(i - 1)), 2) = 1
    then result : adjoin(slist[i], result),
  result);

mypowerset(s) := block([result : {}, n : length(s)],
  for bits : 0 thru 2^n - 1 do result : adjoin(mysubset(bits, s), result);

R(n) := if n = 0 then {} else mypowerset(R(n - 1));

R0(n) := subst(0, {}, R(n));

for i : 0 thru 5 do print(R0(i));
time(%);

102秒かかりました。(表示なしなら89秒)。

ちなみに、組み込みのpowersetを使って、

R(n) := if n = 0 then {} else powerset(R(n - 1));
R(5);

とすると、戻ってきません…

よくよく考えると、集合(要素の単一性)使う理由は{}表記のためだけで、演算はリストでいいなと気がつき、リストで実装してみたら、表示なし、[ ]⇒{ }フォーマット変換の場合78秒。順番は目をつぶってと、endconsをconsに変えたら40秒。
ナイーブな方法だとこんなもんでしょうか。