I think I have correctly implemented Powerset in Clojure.

(use '(clojure set))

(defn powerset [input result]
  (if (nil? (first input))
    (concat result #{})
    (set (reduce concat
           (for [x input]
             (let [set-of-x #{x}
                   input-no-x (set (remove set-of-x input))
                   next-result (union result (set (list input set-of-x input-no-x)))]
               (powerset input-no-x next-result)))))))

Of course I'm interested in how a library function could make the above a one-liner, but I'm also interested in how the above code could be made more idiomatic.

  1. (if (nil? (first input)) feels wrong.
  2. Using the let block to replicate imperative calculations. Acceptable?
  3. Could I use ->> to make the following line more readable? (union result (set (list input set-of-x input-no-x)))
  4. I'm not using recur as I got the "recur must be in the tail position" compiler error.

EDIT Removed (loop) from originally-posted version. - I had erroneously copy-pasted code after I had already commenced attempting to introduce loop/recur (tail recursion). How use loop/recur in this function?

  • \$\begingroup\$ Feedback from @stevelknievel on twitter: use if-let \$\endgroup\$
    – noahz
    Jun 24, 2012 at 3:36
  • 1
    \$\begingroup\$ Library that does the job: math.combinatorics/subsets \$\endgroup\$
    – skuro
    Jun 24, 2012 at 7:45
  • \$\begingroup\$ And it's part of Clojure Contrib. \$\endgroup\$
    – noahz
    Jun 25, 2012 at 14:55

2 Answers 2


A couple of random comments on your code:

  • it doesn't parse correctly, I guess the closed paren right after loop bindings is misplaced. I couldn't run it even after fixing that.

  • why do you need a second input parameter? I would expect the signature to only have the input set as parameter

  • (if (nil (first input)) then else) is more idiomatically written (note the inversion of the then-else branches) (if (seq input) else then)

  • input-no-x can be obtained in a simpler way: (let [input-no-x (disj input x)])

  • \$\begingroup\$ Fixed the code - I had copy-pasted a late attempt at introducing loop \ recur - which didn't work (want to do this). Regarding the second parameter - it's an accumulator for the recursive call, so another improvement is that the function could be overloaded. \$\endgroup\$
    – noahz
    Jun 25, 2012 at 14:58

I know this is an old question, but see the explanation here for a much simpler way:


Code (from https://gist.github.com/796299 )

(defn powerset [ls]
  (if (empty? ls) '(())
      (union (powerset (next ls))
        (map #(conj % (first ls)) (powerset (next ls))))))
  • 2
    \$\begingroup\$ You should save (powerset (next ls)) in a variable rather than computing it twice. :) \$\endgroup\$ Jan 10, 2015 at 20:10

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.