Power Sets

A Power Set of a set S is defined as the set of all possible subsets of S.
The power set has cardinality 2^n , if n is the cardinality of S.

One way to think of an algorithm to generate a power set of a given set, is to use recursion:
Decomposing S = {S\a} ++ {a} , we can obtain a power set of S, if we know the power set of S\a.

For example, suppose the power set of {1} is {1}. Then power set of {1 2} is {1}#{2} where {1}#{2} = [{1} {2} {1 2}]
Similarly, power set of S = power set of {S\a} # {a}.
This lends itself to the following solution implemented in Clojure:

(defn power-set [x]

  

  (defn power-cat [x n]

    (concat x (map #(conj %1 n) x) [[n]]))

  (loop [[f & rest] x acc []]

    (if (isEmpty? rest) acc

      (recur rest (power-cat acc f)))))

It turns out that using higher order functions in Clojure, we can solve this problem more elegantly:

(defn power-set [s]
  (reduce (fn [ss x] (concat ss (map #(conj % x) ss))) [#{}] s))