Boyer–Moore and Misra-Gries Algorithms in Clojure

Description of the problem

The Boyer–Moore majority algorithm, is a probabilistic algorithm that solves the majority problem for any data stream in a single pass using constant memory. Today, I’ll do an implementation in Clojure.

An implementation of Boyer-Moore in clojure

(defn boyer-moore [xs]
   (loop [ys xs
          count 0
          candidate nil]
      (cond (empty? ys) candidate
            (zero? count) (recur (rest ys) 1 (first ys))
            (= (first ys) candidate) (recur (rest ys) (inc count) candidate)
            true (recur (rest ys) (dec count) candidate))))

#'user/boyer-moore

Let us test

(boyer-moore [0 1 1 0 2 2 2 0 0 0 1 0 2 0])

An extension

There is an extension of the Boyer-Moore majority algorithm by Misra and Gries. I’ll implement that too.

An implementation of Misra-Gries in clojure

(defn misra-gries [xs k]
  (loop [ys xs
         counts {}]
    (if (empty? ys)
      (keys counts)
      (let [y (first ys)
            zs (rest ys)]
        (cond
          (get counts y false) (recur zs (merge-with + counts {y 1}))
          (< (count counts) k) (recur zs (merge counts {y 1}))
          true (recur zs (->> (reduce-kv (fn [m k v] (assoc m k (dec v))) {} counts)
                              (filter (fn [[k v]] (> v 0)))
                              (into {}))))))))

#'user/misra-gries