鑑於部分有序集，刪除所有的小件物品

我苦苦尋找編寫一個函數鑑於部分有序集，刪除所有的小件物品

(defn remove-smaller 
    [coll partial-order-fn] 
    ___ 
)

其中partial-order-fn有兩個參數，並返回-1 0或1是他們是一個美麗的，習慣的方法可比較（或更小，相等，更大）或nil。

remove-smaller的結果應該是coll，所有小於coll中任何其他項目的項目都將被刪除。

示例：如果我們定義了一個偏序諸如數字太正常相比，字母，而是一個字母和數字是不可比：

1 < 2 a < t 2 ? a

然後，我們將有：

(remove-smaller [1 9 a f 3 4 z]) 
==> [9 z]

來源

2013-03-22 Blacksad

您可以添加一些示例輸入和輸出嗎？「所有比科爾中其他物品都小的物品都將被移除。」將是一個單一項目的集合，即（最大科爾） – 2013-03-23 00:21:37

當然，我添加了一個例子。實際上，如果物品是部分訂購的（而不是完全訂購），'max'並不意味着什麼。 – Blacksad 2013-03-23 00:26:38

只是一個建議：如何調用函數'remove-mins'而不是'remove-smaller'？當前名稱聽起來像是要刪除比給定元素小的所有條目。 – DaoWen 2013-03-23 00:36:56

在實踐中，我可能只是使用湯姆的回答，因爲沒有算法可以保證好於O（n^2）的最差情況下的表現，而且很容易閱讀。但是如果性能很重要，選擇一種算法，即總是 n^2是不好的，如果你能避免它;下面的解決方案避免了對已知不是最大值的任何項目的重新迭代，因此如果該集合實際上是完全有序的，那麼它可以和O（n）一樣好。（當然，這依賴於順序關係的傳遞性，但是因爲您稱之爲隱含的部分順序）

(defn remove-smaller [cmp coll] 
    (reduce (fn [maxes x] 
      (let [[acc keep-x] 
        ,,(reduce (fn [[acc keep-x] [max diff]] 
           (cond (neg? diff) [(conj acc max) false] 
            (pos? diff) [acc keep-x] 
            :else [(conj acc max) keep-x])) 
          [[] true], (map #(list % (or (cmp x %) 0)) 
              maxes))] 
       (if keep-x 
       (conj acc x) 
       acc))) 
     (), coll))

來源

2013-03-23 09:57:25 amalloy

謝謝，我實際上正在嘗試這種性能感知版本的遞歸函數，但無法做到這一點。 – Blacksad 2013-03-23 14:20:43

(defn partial-compare [x y] 
    (when (= (type x) (type y)) 
    (compare x y))) 

(defn remove-smaller [coll partial-order-fn] 
    (filter 
    (fn [x] (every? #(let [p (partial-order-fn x %)] 
         (or (nil? p) (>= p 0))) 
        coll)) 
    coll)) 

(defn -main [] 
    (remove-smaller [1 9 \a \f 3 4 \z] partial-compare))

這輸出(9 \z)，這是正確的，除非你想返回值是與coll相同的類型。

來源

2013-03-23 02:16:31 tom

謝謝湯姆，由於性能方面的原因，我接受了@amalloy答案，但您的版本非常清晰易讀。我給了它+1。再次感謝。 – Blacksad 2013-03-23 14:21:43

(def data [1 9 \a \f 3 4 \z]) 

(defn my-fn [x y] 
    (when (= (type x) (type y)) 
    (compare x y))) 

(defn remove-smaller [coll partial-order-fn] 
    (mapv #(->> % (sort partial-order-fn) last) (vals (group-by type data)))) 

(remove-smaller data my-fn) 
;=> [9 \z]

潛在剩餘項目的順序可能會有所不同的輸入集合，但之間不存在爲了平等「分區」

來源

2013-03-23 07:10:51 sw1nn

這隻適用，因爲您已經添加了將group-by分成可比性分區的簡單/便宜的假設。 – amalloy 2013-03-23 09:51:06

鑑於部分有序集，刪除所有的小件物品

回答

相關問題