我一直在嘗試將（很多）資料庫索引建議提煉成一組適用于大多數資料庫的索引。要做到這一點，我需要解決一個非常基本但 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在其他集合中找不到的唯一單例集合
- 這可以在基本演算法之外完成
I have been trying to translate this into Clojure as a loop-recur function, but couldn't get the basic version of it to work, since there are niggling paradigm gaps between the two languages.
Does anyone have suggestions how I could go about solving this problem in Clojure, either by tips how to convert the python algorithm successfully, or which other Clojure (or even Java) libraries I could use and how ?
uj5u.com熱心網友回復：
這是貪婪集覆寫演算法的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' (remove #{x} xs)
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})
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/448929.html