See also this thread:
http://groups.google.com/group/clojure/browse_thread/thread/134642cc76de17f7?hl=en#
where I also proposed putting power-set in clojure.contrib. I'm just
waiting to hear back from Rich about a few potential changes to core,
and then I will dump all of my remaining proposals on the contrib
issues page.
As far as the return values, mine returns vectors ... I don't think it
really matters if its lists or vectors or seqs, so long as it's
consistent. (I would actually vote against using sets though, since
with the other options it's slightly more general as it will also work
with multi-sets):
(defn power-set
"Returns a lazy seq of possible subvectors of seq s."
[s]
(loop [s (seq s), sets [[]]]
(if s
(recur (rest s) (lazy-cat sets (map #(conj % (first s))
sets)))
sets)))
user> (power-set '(1 1))
([] [1] [1] [1 1])
-Jason
On Jan 23, 12:35 am, Mark Engelberg <mark.engelb...@gmail.com> wrote:
> The power set of a set S is defined as the set of all subsets of S.
>
> Here is one possible implementation of a powerset function. To stay
> true to the spirit of the above definition, I've written it in a way
> that manipulates the sets in set form as much as possible (not quite
> an easy task since things like rest and map return sequences, not
> sets).
>
> (defn powerset [s]
> (if (empty? s) #{#{}}
> (let [element (first s),
> rest-s (disj s element),
> powerset-rest-s (powerset rest-s)]
> (clojure.set/union powerset-rest-s
> (into #{} (map #(conj % element)
> powerset-rest-s))))))
>
> Example: (powerset #{1 2 3}) prints as #{#{} #{1} #{2} #{3} #{1 2} #{1
> 3} #{2 3} #{1 2 3}}
>
> Now, here's the puzzle. Let's say you want to convert this idea over
> to working with lists, or perhaps sequences in general.
>
> Should (powerset '(1 2 3)) print as:
> (() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))
> or
> (nil (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3))
>
> I can think of several excellent arguments for and against each
> option. I'd like to know whether the Clojure community is as
> conflicted on this point as I am. I think that the way you reason
> about this question says a lot about how you view the relationship
> between lists and sequences and the role of nil and the empty list, so
> I look forward to hearing the responses. Let the debating begin!
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
