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

## No comments:

## Post a Comment