# Powerset of collection in Clojure

Similar to this question, here's another implementation. Assume the input is already a set.

 (defn powerset
[set]
(reduce
(fn [xs x] (concat xs (map #(cons x %) xs)))
[()]
set))


There isn't a whole lot here to comment on. I'll just mention a few things:

• Technically, from my quick search of what a powerset is, this function should return sets. That seems petty, but unless it's documented to return a lazy list of lazy lists, users may try to treat the "subsets" as sets (like using them as functions). I'd finish this function off by mapping set over the list.

• But to do that, you should rename your parameter, as you're shadowing the build-in set.

• After doing the above two, it developed quite long lines and became nested. I'd add in some use of ->>, and put a few of the lines on the next line.

After that, I ended up with:

(defn powerset [base-set]
(->> base-set
(reduce
(fn [xs x]
(concat xs
(map #(cons x %) xs)))
[()])

(map set)))

• You can construct the sets directly. Replace #(cons x %) with #(conj % x) and [()] with [#{}]. Then you don't need the final (map set). This works whatever kind of collection base-set is. – Thumbnail Feb 12 '19 at 15:40
• @Thumbnail You're right. I wrote this answer quickly on my phone on a train on the way to get my hair cut. I could have dug further. I think your suggestion merits a new answer. – Carcigenicate Feb 12 '19 at 17:09
• No. You take it. It's a detail. But it's still not quite right. If you supply a sequence with repeats, you get some identical subsets. I think the cure is to replace [()] with [(empty base-set)]. What it produces from a sequence may not be the traditional idea of a powerset, but at least all the elements of the answer are different. Alternatively, you could start with (set base-set), a trivial operation compared with what's to come. – Thumbnail Feb 12 '19 at 17:57