CODEWITHSUNDEEP
clojure
Snehaa Ganesan
Snehaa Ganesan

Reputation: 509

How to compare values of consecutive elements in a vector for filtering?

I need to filter a given vector such that the output contains only those elements that are not a duplicate of an immediate neighbor. 

Example : I/P -> [1 1 3 2 2 4 5 5]
          O/P -> [3 4]

Upvotes: 2

Views: 887

Answers (7)

optevo
optevo

Reputation: 2104

(def data-1 [1 1 3 2 2 4 5 5])

(def data-2 [1 1 3 2 2 4 5 5 2 5 5])

(defn reducer [[v p] n]
  (cond
    (empty? v) [[n] n]
    (= (peek v) n) [(pop v) n]
    (= n p) [v n]
    :else [(conj v n) n]))

(first (reduce reducer [[] nil] data-1))
;[3 4]

(first (reduce reducer [[] nil] data-2))
;[3 4 2]

Note that this solution also covers cases where there are more than 2 adjacent values that are the same such as:

(def data-3 [1 1 3 2 2 2 4 5 5 2 5 5])
;[3 4 2]

All the hard work goes on in the function reducer.

Mentally I always tag the first parameter of reduce as "the accumulator" and the second as "the new value".

In this case, the accumulator has to have two parts: the vector that you are creating and the last number seen. (Note that if you only expect duplicates to occur as pairs, the last number seen is not necessary.)

So the [v p] is "the accumulator" part of the reducer - v is the vector you are creating and p is the previous value seen. The n parameter is "the new value".

The explanation of the 4 conditions is:

  1. If v is empty, just make a new vector with the new value and record the new value. This is necessary because peek on an empty vector (the next condition) will result in an exception.
  2. If the last value of v is the same as the new value, remove it and record the new value.
  3. If the new value (n) is the same as the last value (p) ignore it. This condition enables us to eliminate values that are repeated several times.
  4. If none of these conditions are true it's ok to append the value :)

Upvotes: 2

Snehaa Ganesan
Snehaa Ganesan

Reputation: 509

Another way to do this : 

(defn remove-consecutive-duplicates [inp]
    (let [intm (into [] (partition-by identity inp))]
             (reduce (fn [acc n]
                (if (= 1 (count n))
                  (conj acc n)
                  acc ))
              [] intm)))

Do note that dedupe does not give the desired output.

Upvotes: 0

Thumbnail
Thumbnail

Reputation: 13483

Building it more or less from the ground up, you can get destructuring to do much of the work: 

(defn no-dupes [coll]
  (when-let [[x & [y & ys :as xs]] (seq coll)]
    (if xs
      (if (= x y)
        (recur (drop-while #(= x %) ys))
        (lazy-seq (cons x (no-dupes xs))))
      (list x))))

Having said that, I made two errors in these few lines, whereas Alan Malloy's answer is transparently correct.

Is this is any faster than @dpassen's neat transducer version?

Yes. It's about three times as fast: about 500 nano seconds compared to about 1.5 micro seconds for the short example, according to Criterium.

Upvotes: 1

dpassen
dpassen

Reputation: 1306

Using transducers like @amitr's solution, but IMHO, a little cleaner:

(def isolate
  (comp
   (partition-by identity)
   (remove next)
   cat))

It can then be used with sequence, into, whichever transducer-accepting function you desire.

Upvotes: 4

amitr
amitr

Reputation: 890

This is exactly the same logic as @amalloy's answer, but it uses transducers instead of the threading macro (->>).

(defn isolate [coll]
  (transduce
   (comp
   (partition-by identity)
   (remove next)
   (map first))
  conj coll))

It should be more efficient, at least on large collections.

The partition-by identity partitions coll to sub-lists of identical elements. The remove next drops all sub-lists whose next is not nil (i.e., they have more than one element). The last map first takes the first element of each sub-list, thus flattening the list of lists to a list of elements.

Just run each of the steps separately to see how it works.

Upvotes: 7

jas
jas

Reputation: 10865

This is pretty much a brute force solution so hopefully we'll see some more satisfying answers, but to get the ball rolling ...

(defn lonely? 
  "Return the ith element of v if it doesn't have a matching neighbor"
  [i v]
  (when (cond
          (zero? i) (not= (v 0) (v 1))
          (= i (- (count v) 1)) (not= (v i) (v (- i 1)))
          :else (and (not= (v i) (v (- i 1)))
                     (not= (v i) (v (+ i 1)))))
    (v i)))

> (def v [1 1 3 2 2 4 5 5])

> (keep #(lonely? % v) (range (count v)))
(3 4)

Upvotes: 2

amalloy
amalloy

Reputation: 92147

(defn isolated [coll]
  (->> coll
       (partition-by identity)
       (remove next)
       (map first)))

Upvotes: 8

Related Questions