Skip to content

Instantly share code, notes, and snippets.

@cs224
Last active December 20, 2015 14:48
Show Gist options
  • Save cs224/6149244 to your computer and use it in GitHub Desktop.
Save cs224/6149244 to your computer and use it in GitHub Desktop.
;;; The solution relies on the following implementation of the partitions function:
;;; https://gist.github.com/ray1729/5830608
(defn partition-combination-sets [partition]
(let [partition (vec partition)
c (count partition)]
(for [i (range 1 (inc c))
combination (combinatorics/combinations (range c) i)]
;; the following (map partition combination) may be a bit confusing, because it does use the vector
;; defined above as a function and has nothing to do with the standard partition function of the clojure core language.
(apply union (map partition combination)))))
(defn does-partition-cover-set-of-sets [partition set-of-sets]
(let [pcss (partition-combination-sets partition)]
(every? identity(map (fn [s] (some (fn [pcs] (= pcs s)) pcss)) set-of-sets))))
(defn smallest-partition-that-covers-set-of-sets [set-of-sets]
(let [all-element-set (reduce union set-of-sets)
all-partitions (partitions all-element-set)]
(apply (partial min-key (fn [p] (count p)))
(filter (fn [partition] (does-partition-cover-set-of-sets partition set-of-sets)) all-partitions))))
(smallest-partition-that-covers-set-of-sets #{#{1 2 3} #{1 2 4} #{1 2 5}})
-> #{#{1 2} #{3} #{4} #{5}}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment