Powerset in Clojure

Question

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?

• noahz: Feedback from @stevelknievel on twitter: use if-let
• skuro: Library that does the job: math.combinatorics/subsets
• noahz: And it's part of Clojure Contrib.

Answer 1

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)])

• noahz: 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.

Answer 2

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

http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch1/solutions/recursionSol.html

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

(defn powerset [ls]
 (if (empty? ls) '(())
 (union (powerset (next ls))
 (map #(conj % (first ls)) (powerset (next ls))))))

• Gordon Gustafson: You should save (powerset (next ls)) in a variable rather than computing it twice. :)