Common elements in two lists with duplicates

Question

I want to find the common elements in two [lists, vectors, sequences] when there can be duplicates.

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

Here is what I currently have:

(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)))))

My experience with 4clojure has shown me that I rarely write the most idiomatic or succinct code so I'm interested in finding out whether there is a better way of doing this.

Answer 1

Here's my implementation. It uses maps and sets to hold intermediate data, and thus is not lazy like your version, but I think it is more readable and will have better overall performance characteristics (your version has quadratic time complexity to realize the results from common-elements).

(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

Not the most efficient, but fairly concise:

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

Returns maps of values and counts

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

Another approach, modified from my own question 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)))

which returns a vector as in the original question

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

Of course if you know your inputs are sorted, you may omit the sort, and if you furthermore know they are vectors you can use the optimizations provided by amalloy in answer to the referenced question.

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)))

The function is similar to the ones given in previous answers. I still submit this answer for Clojure beginners who may stumble on this question. I believe the function makes clearer the steps needed for the function to evaluate to a result.