Clojure中的最小"集覆盖"解决方案

Question

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

这意味着，给定一组集合，选择覆盖某个域u的集合s的子集，但如果没有给定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，但由于两种语言之间存在微小的范式差距，因此无法使其基本版本发挥作用。

有没有人建议我如何在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})