How to diff/substract two lists in Clojure

Question

Example:

1 1 1 3 3 4 4 5 5 6  L1
1     3 3   4 5      L2
  1 1     4     5 6  Res

Constraints:

1. The diff/subtract is defined as the "set" of elements from L1 minus (∖) L2
2. L2 is always a subset (⊆) of L1
3. The elements in L1 and L2 can have duplicates
4. The elements are primitives (int, string) and all of the same type

(clojure.set/difference) doesn't help here because of (3).

Answer 1

(defn diff [s1 s2]
  (mapcat
    (fn [[x n]] (repeat n x))
    (apply merge-with - (map frequencies [s1 s2]))))

For example, given

(def L1  [1 1 1 3 3 4 4 5 5 6])
(def L2  [1     3 3   4 5 ])

then

(diff L1 L2)
;(1 1 4 5 6)

Answer 2

Here is one way to do it. Steps:

1.Find the frequencies for each list
2.Diff the frequencies
3.Repeat each element for the remaining value of frequency.


(defn myminus [s1 s2]
  (let [g1 (frequencies s1)
        g2 (frequencies s2)
        m (merge-with - g1 g2)
        r (mapcat #(repeat (second %) (first %)) m)]
    r))

Answer 3

If inputs are in order, as they appear to be, then you can do this lazily

(defn sdiff 
  [[x & rx :as xs] [y & ry :as ys]]
  (lazy-seq 
    (cond
      (empty? xs) nil
      (empty? ys) xs
      :else (case (compare x y)
              -1 (cons x (sdiff rx ys))
               0 (sdiff rx ry)
              +1 (sdiff xs ry)))))

---

Given example:

(def L1 [1 1 1 3 3 4 4 5 5 6])
(def L2 [1 3 3 4 5])
(sdiff L1 L2) ;=> (1 1 4 5 6)

Lazy-sequence of numbers that are not Fibonacci numbers. (Notice we don't require constraint #2 -- the repeated 1's in the Fibonacci numbers do not cause a problem.)

(defn fibs [] (map first (iterate (fn [[c n]] [n (+ c n)]) [0 1])))

(take 20 (sdiff (range) (fibs)))
;=> (4 6 7 9 10 11 12 14 15 16 17 18 19 20 22 23 24 25 26 27)

Answer 4

Since L2 is always a subset of L1 you can group-by on both lists and just emit the key as many times as the difference is between the counts of each grouping.

(def L1 (list 1 1 1 3 3 4 4 5 5 6))
(def L2 (list 1     3 3   4 5    ))

(defn diff [l1 l2]
  (let [a (group-by identity l1)
        b (group-by identity l2)]
    (mapcat #(repeat
              (-
               (count (second %))
               (count (get b (key %))))
              (key %)) a)))


(diff L1 L2)
;;(1 1 4 5 6)

Answer 5

(defn diff-subtract
"The diff-subtract is defined as the sum of elements from L1 minus L2"
[list1 list2]
(let [l1 (into {} (map #(vector (first %) %) (partition-by identity (sort list1))))
      l2 (into {} (map #(vector (first %) %) (partition-by identity (sort list2))))]
     (-> (map
          #(repeat (- (count (l1 %)) (count (l2 %))) %)
           (range 1 (inc (apply max (map first l1)))))
     flatten)))

(diff-subtract [1 1 1 3 3 4 4 5 5 6] [1 3 3 4 5]) => (1 1 4 5 6)