1
\$\begingroup\$

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))
\$\endgroup\$
1
\$\begingroup\$

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)))
\$\endgroup\$
  • \$\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 Feb 12 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\$ – Carcigenicate Feb 12 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 Feb 12 at 17:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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