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

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

1 Answer 1


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
         (fn [xs x] 
           (concat xs
                   (map #(cons x %) xs)))

       (map set)))
  • \$\begingroup\$ 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. \$\endgroup\$
    – Thumbnail
    Commented Feb 12, 2019 at 15:40
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Feb 12, 2019 at 17:09
  • \$\begingroup\$ 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. \$\endgroup\$
    – Thumbnail
    Commented Feb 12, 2019 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.