Clojure中的最小“集隐蔽”解

Question

我一直在尝试将(许多)数据库索引建议提取为一组适用于大多数数据库的索引。要做到这一点，我需要解决一个非常基本但NP完全集理论问题：最小集覆盖问题。

这意味着，给定一组集合，选择一个集s的子集，该子集涵盖特定的域u，但是如果u没有给出，则使其成为s的联合。集的最优子集是达到某一极小值的子集，通常是集的最小数量，但如果加权的话，集合的总权重也可以是最小的。

(def s #{#{1 4 7} #{1 2} #{2 5 6} #{2 5} #{3} #{8 6}})
(def u (apply set/union s))
(set-cover s u)
=> (#{7 1 4} #{6 2 5} #{3} #{6 8})

我使用clojure.math.combinatorics实现了一个简单的版本，它依赖于它返回的子集，顺序是增加集合的数量。

(defn set-cover
  ([s]
   (set-cover s (apply set/union s)))
  ([s u]
   (->> s
        (combo/subsets)
        (filter (fn [s] (= u (apply set/union s))))
        first)))

然而，对于较大的s来说，这是非常缓慢的，因为NP性质和反复出现的联合(甚至优化的)。对于我的用例来说，支持加权集的版本也会更好。

看看优化的版本，大多数的线索最终在论文的土地，遗憾的是，我不够聪明。我在SO上找到了这个小python实现

def setCover(setList,target=None):
    if not setList: return None
    if target  is None: target  = set.union(*setList)
    bestCover = []
    for i,values in enumerate(setList):
        remaining = target - values
        if remaining == target: continue
        if not remaining: return [values]
        subCover = setCover(setList[i+1:],remaining)
        if not subCover: continue
        if not bestCover or len(subCover)<len(bestCover)-1:
            bestCover = [values] + subCover
    return bestCover

它滴答作响许多盒子：

• 递归工作
• 将部分结果与优化结果进行比较
• 似乎适合不同的最低定义:计数或重量
• 有更多的优化，我可以让
  • 它可以在基本算法之外执行。
    • 将输入集排序在较高的最小分数(大小、重量)上
    • 标识u中其他集合中找不到的唯一单例集

我一直在尝试将它转换为loop-recur函数，但由于这两种语言之间存在着微小的范例差距，所以无法使它的基本版本正常工作。

有没有人建议我如何在Clojure中解决这个问题，或者通过技巧如何成功地转换python算法，或者我可以使用哪些其他Clojure (甚至Java)库，以及如何使用？

Answer 1

下面是贪心集覆盖算法的Clojure版本，即选择一个集，它在每次迭代中覆盖最不暴露的元素。它不是使用loop/recur构建完整的结果，而是延迟地使用lazy-seq返回每个结果元素。

(defn greedy-set-cover
  ([xs]
   (greedy-set-cover xs (apply set/union xs)))
  ([xs us]
   (lazy-seq
     (when (seq us)
       (let [x (apply max-key #(count (set/intersection us %)) xs)
             xs' (disj xs x)
             us' (set/difference us x)]
         (cons x (greedy-set-cover xs' us')))))))

(def s #{#{1 4 7} #{1 2} #{2 5 6} #{2 5} #{3} #{8 6}})

(greedy-set-cover s)   ;; = (#{7 1 4} #{6 2 5} #{6 8} #{3})