Intersection of two lists in clojure

Question

context: this is somewhat related to project euler problem 5, which is:

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I apply prime number decomposition to the range of numbers from 1 to 20, and the product of all that should be the smallest number.

(absorb '(2 2 2) '(2 3 4)) -> '(2 2 2 3 4) ;; does not have to be sorted

(defn absorb [seq1 seq2]
  (loop [s1 (sort seq1)
         s2 (sort seq2)
         acc '()]
    (let [s1-curr (first s1)
          s2-curr (first s2)]
      (cond (and (empty? s1) (empty? s2)) acc
            (empty? s1) (into s2 acc)
            (empty? s2) (into s1 acc)
            (= s1-curr s2-curr) (recur (rest s1) (rest s2) (cons s1-curr acc))
            :else (recur (rest s1) s2 (cons s1-curr acc))))))

Is there a way to write this in more idiomatic Clojure, or a more optimized/clea er version?

Answer 1

My assumption is that you want to keep the maximal count so that if 2 occurs 4 times in one list and 2 occurs 3 times in another, 2 will appear 4 times in the result.

In this case, I would write the following:

(defn elem-counts [coll]
   (reduce (fn [acc val] (assoc acc val (inc (acc val 0)))) {} coll))

With this, I can get the map from values in the collection to the number of times it occurs.

Now, for a way to reverse this process (from a map of counts to the list that would create the map):

(defn seq-from-counts [count-map]
   (flatten (for [[k v] count-map] (repeat v k))))

Finally, your intersect becomes:

(defn absorb [list1 list2]
   (seq-from-counts (merge-with max 
                                (elem-counts list1) 
                                (elem-counts list2))))

Answer 2

This is an extended comment on @HemanGandhi's answer.

• The elem-counts function is just the standard frequencies function.
• There is no need to regenerate the list: seq-from-counts is redundant. Just work with the frequency maps, which are functioning as multisets.