Clojure 中最小的 `set cover` 解决方案

Question

我一直在尝试将（很多的）数据库索引建议提炼成一组适用于大多数数据库的索引。为此，事实证明我需要解决一个非常基本但 NP 完全集理论问题：minimum set cover problem.

这意味着给定一组集合，select 集合的子集 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)))

然而，由于 NP 性质和循环联合（甚至是优化的联合），这在较大的 s 上非常慢。对于我的用例，支持加权集的版本也更可取。

研究优化版本后，大多数路径都进入了论文领域，遗憾的是我不够聪明。我在 SO

上找到了这个小

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 来构建完整的结果，而是懒惰地 returns 每个结果元素使用 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})

Clojure 中最小的 `set cover` 解决方案

Minimal `set cover` solution in Clojure

recursion

clojure

np

set-cover