set-cover.clj

;; problem representation
;; {:L 5
;;  :S { 0 #{1 2}
;;       1 #{1 5 3}
;;       2 #{2 3} }}

(defn combos
  [n s]
  (letfn
    [(expand
      [[a b]]
      (when-not
        (empty? b)
        (cons
         [(conj a (first b))
          (rest b)]
         (expand [a (rest b)]))))]
    (if (zero? n)
      (list [[] s])
      (mapcat
        expand
        (combos (dec n) s)))))

(defn gen-problem
  [s l]
  {:L l
   :S (into
       {}
       (for [s (range s)]
         [s (set
             (take
              (inc (rand-int (- l 3)))
              (shuffle
               (range l))))]))})


(defn greedy-solve
  [{:keys [L S]}]
  (loop [l-off (set (range L))
         s-ons #{}
         S     S]
    (cond
     (empty? l-off) s-ons
     (empty? S)     :unsolvable
     :else          (let [[k v] 
                          (apply
                            max-key
                            (fn [[k v]]
                              (count
                                (clojure.set/intersection
                                  l-off
                                  v)))
                            S)]
                      (recur
                       (clojure.set/difference l-off v)
                       (conj s-ons k)
                       (dissoc S k))))))


(defn brute-solve
  [{:keys [L S]}]
  (let [slns (filter
               (fn [c]
                 (=
                   (set (range L))
                   (apply
                     clojure.set/union
                     (vals
                       (select-keys
                         S
                         c)))))
               (for [n (range 1 (count S))
                     c (map
                         first
                         (combos n (range (count S))))] 
                 (set c)))]
    (if (empty? slns) :unsolvable
      (apply
        min-key
        count
        slns))))