Clojureらしいpowerset

[ken.coba]

小林です。

Clojureのライブラリにはpowersetを作る関数がないのかな？
と思って、powerset関数を作ってみました。

https://gist.github.com/796299

Clojureらしくもなんともないので、
さらにコンパクトなコードがあれば教えていただけるとありがたいです。

http://gnuvince.wordpress.com/2008/10/11/cribbage-points-counter-in-clojure/
こんなところにもあったりするんですけど、nthを使いたくないんですよね。

[Takahiro]

こんばんは。穂積です。

https://gist.github.com/797041
遅延シーケンスを返すようにしたら、だらだらと長くなってしまいました。
冪集合なんだから集合で返した方がいいのかもしれないですが、入力に重複がない事を前提とするなら遅延シーケンスでも正しい結果を返せるので私はこの方が嬉しいです。
小林さんの方法では同じ引数の再帰が2箇所がある点と、unionの引数にシーケンスを与えてる点が良くないと思います。
unionの引数は集合を想定しているので、シーケンスを与えると重複を許してしまいます。
引数のリストには重複がない事を前提とするなら、concat でいいと思います。

reduceを使うとコンパクトなので、集合を返す場合はこっちの方がいいかもしれません。
(defn powerset [ls]
(reduce (fn [acc elem] (union acc (set (map #(conj % elem) acc)))) #{#{}} ls))

2011年1月26日15:02 ken.coba <ken....@gmail.com>:

[deltam]

こんにちは、deltamです。
べき集合（Powerset）を作る関数ということですが、Contribライブラリに使えるそうな関数を見つけたので試してみました。

http://richhickey.github.com/clojure-contrib/combinatorics-api.html

このc.c.combinatoricsというライブラリだと組合せ処理で使える関数がまとまってます。
このなかのsubsetsというのがべき集合を作ってくれます。

いろいろ試してみるとこんな感じになりました。
https://gist.github.com/798153

ちゃんと遅延シーケンスで返してくれるし、ちょっと使ってみるにはsubsetsも良いんじゃないでしょうか。

On 1月27日, 午前2:57, Takahiro <fat...@googlemail.com> wrote:
> こんばんは。穂積です。
>
> https://gist.github.com/797041
> 遅延シーケンスを返すようにしたら、だらだらと長くなってしまいました。
> 冪集合なんだから集合で返した方がいいのかもしれないですが、入力に重複がない事を前提とするなら遅延シーケンスでも正しい結果を返せるので私はこの方が嬉しい です。
> 小林さんの方法では同じ引数の再帰が2箇所がある点と、unionの引数にシーケンスを与えてる点が良くないと思います。
> unionの引数は集合を想定しているので、シーケンスを与えると重複を許してしまいます。
> 引数のリストには重複がない事を前提とするなら、concat でいいと思います。
>
> reduceを使うとコンパクトなので、集合を返す場合はこっちの方がいいかもしれません。
> (defn powerset [ls]
> (reduce (fn [acc elem] (union acc (set (map #(conj % elem) acc)))) #{#{}} ls))
>

> 2011年1月26日15:02 ken.coba <ken.c...@gmail.com>:

>
>
>
>
>
>
>
> > 小林です。
>
> > Clojureのライブラリにはpowersetを作る関数がないのかな？
> > と思って、powerset関数を作ってみました。
>
> >https://gist.github.com/796299
>
> > Clojureらしくもなんともないので、
> > さらにコンパクトなコードがあれば教えていただけるとありがたいです。
>

> >http://gnuvince.wordpress.com/2008/10/11/cribbage-points-counter-in-c...
> > こんなところにもあったりするんですけど、nthを使いたくないんですよね。

[ken.coba]

小林です。

穂積さん、deltamさんありがとうございます！

うーむ、自分はまだreduceの使い処が分かってないってことが分かりました。

「subsets」って、確かに部分集合の集合を返すってことですね。

ありがとうございます。