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)