Общие элементы в двух списках с дубликатами

Question

Я хочу найти общие элементы в двух [списках, векторах, последовательностях], когда могут быть дубликаты.

(common-elements [1] [1]) ; [1] 
(common-elements [1 2] [1 1]) ; [1] 
(common-elements [1 1] [1 1 1]) ; [1 1] 

Вот что я в настоящее время:

(defn remove-first [elem coll] 
    (lazy-seq 
    (when-let [s (seq coll)] 
     (let [f (first s), r (rest s)] 
     (if (= elem f) 
      r 
      (cons f (remove-first elem r))))))) 

(defn common-elements [coll1 coll2] 
    (lazy-seq 
    (when (and (seq coll1) (seq coll2)) 
     (let [f (first coll1)] 
     (if (some #{f} coll2) 
      (cons f (common-elements (rest coll1) 
            (remove-first f coll2))) 
      (common-elements (rest coll1) coll2))))) 

Моего опыт 4clojure показал мне, что я редко пишу наиболее идиоматический или сжатый код, так что я интересно узнать, есть ли лучший способ сделать это.

Answer 1

Вот моя реализация. Он использует карты и наборы для хранения промежуточных данных и, следовательно, не ленив, как ваша версия, но я думаю, что это более читаемо и будет иметь лучшие общие характеристики производительности (ваша версия имеет квадратичную сложность во времени для реализации результатов от общих элементов).

(require '[clojure.set :as set]) 
(defn common-elements [& colls] 
    (let [freqs (map frequencies colls)] 
    (mapcat (fn [e] (repeat (apply min (map #(% e) freqs)) e)) 
      (apply set/intersection (map (comp set keys) freqs))))) 

Answer 2

Не самый эффективный, но довольно кратким:

(defn common [& ss] 
    (let [fs (map frequencies ss), ks (map set ss)] 
    (select-keys (apply merge-with min fs) 
       (reduce clojure.set/intersection ks)))) 

Возвращает карты значений и отсчитывает

(common [1] [1]) ;=> {1 1} 
(common [1 2] [1 1]) ;=> {1 1} 
(common [1 1] [1 1 1]) ;=> {1 2} 

Другой подход, модифицированный из моего собственного вопроса Idiomatic/Efficient Clojure way to intersect two a priori sorted vectors?,

(defn common [x y] 
    (loop [x (sort x) y (sort y) acc []] 
    (if (and x y) 
     (let [x1 (first x) 
      y1 (first y)] 
     (cond 
     (< x1 y1) (recur (next x) y acc) 
     (> x1 y1) (recur x (next y) acc) 
     :else (recur (next x) (next y) (conj acc x1)))) 
    acc))) 

который возвращает вектор, как в исходном вопросе

(common [1 1 1 2 2 3] [1 1 2 5]) ;=> [1 1 2] 

Конечно, если вы знаете, что ваши входы сортируются, вы можете опустить sort, и если вы знаете, что они, кроме того, векторы можно использовать оптимизацию, предоставляемые amalloy в ответ на который ссылается вопрос.

Answer 3

(defn get-commons [l1 l2] 
    (let [f1 (frequencies l1) 
     f2 (frequencies l2) 
     common (clojure.set/intersection (set l1) (set l2)) 
     love (merge-with (fn [val1 val2] (min val1 val2)) f1 f2)] 
    (mapcat #(repeat (love %) %) common))) 

Функция похожа на те, которые даны в предыдущих ответах. Я по-прежнему представляю этот ответ новичкам Clojure, которые могут наткнуться на этот вопрос. Я считаю, что функция делает более четкие шаги, необходимые для оценки функции для результата.