{"id":1281,"date":"2013-12-10T05:00:55","date_gmt":"2013-12-10T13:00:55","guid":{"rendered":"http:\/\/zackmdavis.net\/blog\/?p=1281"},"modified":"2013-12-09T13:58:19","modified_gmt":"2013-12-09T21:58:19","slug":"computing-the-powerset","status":"publish","type":"post","link":"http:\/\/zackmdavis.net\/blog\/2013\/12\/computing-the-powerset\/","title":{"rendered":"Computing the Powerset"},"content":{"rendered":"<p>Suppose we want to find the powerset of a given set, that is, the set of all its subsets. How might we go about it? Well, the powerset of the empty set is the set containing the empty set.<\/p>\n<p><p style='text-align:center;'><span class='MathJax_Preview'><img src='http:\/\/zackmdavis.net\/blog\/wp-content\/plugins\/latex\/cache\/tex_ed7288f815608d74ba2bde0581d30b6c.gif' style='vertical-align: middle; border: none;' class='tex' alt=\"\\mathcal{P}(\\emptyset)=\\{\\emptyset\\}\" \/><\/span><script type='math\/tex;  mode=display'>\\mathcal{P}(\\emptyset)=\\{\\emptyset\\}<\/script><\/p><\/p>\n<p>And the powerset of the union of a set <em>S<\/em> with a set containing one element <em>e<\/em>, is just the union of the powerset of <em>S<\/em> with the set whose elements are like the members of the powerset of <em>S<\/em> except that they also contain <em>e<\/em>.<\/p>\n<p><p style='text-align:center;'><span class='MathJax_Preview'><img src='http:\/\/zackmdavis.net\/blog\/wp-content\/plugins\/latex\/cache\/tex_1491b7841e9f0cad24d7e4ccaa549adb.gif' style='vertical-align: middle; border: none;' class='tex' alt=\"\\mathcal{P}(S\\cup\\{e\\})=\\mathcal{P}(S)\\cup\\{t\\cup\\{e\\}\\}_{t\\in\\mathcal{P}(S)}\" \/><\/span><script type='math\/tex;  mode=display'>\\mathcal{P}(S\\cup\\{e\\})=\\mathcal{P}(S)\\cup\\{t\\cup\\{e\\}\\}_{t\\in\\mathcal{P}(S)}<\/script><\/p><\/p>\n<p>So in Clojure we might say<\/p>\n<pre><code>(require 'clojure.set)\r\n\r\n(defn include-element [collection element]\r\n  (map (fn [set] (clojure.set\/union set #{element}))\r\n       collection))\r\n\r\n(defn powerset [set]\r\n  (if (empty? set)\r\n    #{#{}}\r\n    (let [subproblem (powerset (rest set))]\r\n      (clojure.set\/union subproblem\r\n                         (include-element subproblem\r\n                                          (first set))))))\r\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Suppose we want to find the powerset of a given set, that is, the set of all its subsets. How might we go about it? Well, the powerset of the empty set is the set containing the empty set. And &hellip; <a href=\"http:\/\/zackmdavis.net\/blog\/2013\/12\/computing-the-powerset\/\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[20],"tags":[70,36],"_links":{"self":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/1281"}],"collection":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/comments?post=1281"}],"version-history":[{"count":5,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/1281\/revisions"}],"predecessor-version":[{"id":1286,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/posts\/1281\/revisions\/1286"}],"wp:attachment":[{"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/media?parent=1281"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/categories?post=1281"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/zackmdavis.net\/blog\/wp-json\/wp\/v2\/tags?post=1281"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}