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 [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
