Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
402 - PurelyFunctional.tv Newsletter

Most frequent element

Write a function that takes a collection and returns the most frequent element. But here's the thing: you can't use the built-in function clojure.core/frequencies. And if there are ties, just pick one.

Examples

(most-frequent [2 2 3 4 4 2 1 1 3 2]) ;=> 2
(most-frequent []) ;=> nil
(most-frequent [1 1 4 4 5]) ;=> 4

Notes

  • return nil for an empty collection
  • in the case of a tie, return one of the winners

Thanks to this site for the challenge idea where it is considered Very Hard level in JavaScript.

Please submit your solutions as comments on this gist.

@sztamas
Copy link

sztamas commented Nov 3, 2020

(defn most-frequent [coll]
  (when (seq coll)
    (->>
      coll
      (group-by identity)
      (apply max-key (comp count second))
      first)))

@zugnush
Copy link

zugnush commented Nov 3, 2020

(defn most-frequent
  [col]
  (-> (for [[k v] (group-by identity col)]
          [(count v) k])
      sort
      last
      second))

@patinside
Copy link

patinside commented Nov 3, 2020

(defn most-frequent
  [coll]
  (->> coll 
       (group-by identity)
       (sort-by second)
       (last)
       (first)))

@NPException
Copy link

NPException commented Nov 3, 2020

(defn most-frequent
  [xs]
  (some->>
    (reduce                                                 ;; 1) get counts for each element
      (fn [m k] (assoc m k (inc (get m k 0))))
      nil                                                   ;; (will return nil for 0 elements, ending the some->> macro)
      xs)
    (apply max-key val)                                     ;; 2) find entry with highest count
    key))                                                   ;; 3) return the key of the entry

I only realized after I finished writing the function, that my reduce step is very similar to how frequencies is implemented... 🤷‍♂️

@nwjsmith
Copy link

nwjsmith commented Nov 3, 2020

(defn most-frequent
  "Takes a collection and returns the most frequent element."
  [coll]
  (let [frequencies (reduce (fn [counts x] (update counts x (fnil inc 0)))
                            {}
                            coll)]
    (when-let [entry (last (sort-by val frequencies))]
      (key entry))))

@frankadrian314159
Copy link

frankadrian314159 commented Nov 3, 2020

(defn frequency-map
  "If life doesn't give you frequencies, roll your own."
  [s]
  (apply (partial merge-with +) (map (fn [x] {x 1}) s)))

(defn sort-by-val
  "Sort the map by map value. Shamelessly
   modified from sorted-map-by's documentation.
   Now works with multiple types."
  [m]
  (into (sorted-map-by (fn [key1 key2]
                         (compare (get m key2)
                                  (get m key1)))) m))

(defn most-frequent [seq]
  (-> seq
      frequency-map
      sort-by-val
      first
      first))

@michelemendel
Copy link

michelemendel commented Nov 3, 2020

(defn most-frequent [xs]
  (first (last 
           (sort-by (comp count second) 
                        (group-by identity xs)))))

@mchampine
Copy link

mchampine commented Nov 3, 2020

(defn most-frequent [coll]
  (first (last (sort-by count (partition-by identity (sort coll))))))

@miner
Copy link

miner commented Nov 3, 2020

(defn most-frequent [coll]
  (when-let [gs (seq (vals (group-by identity coll)))]
    (peek (apply max-key count gs))))

@stuartstein777
Copy link

stuartstein777 commented Nov 3, 2020

(defn most-frequent [xs]
  (if (empty? xs)
    nil
   (->>
     (group-by identity xs)
     (vec)
     (sort-by #(count (second %)))
     (last)
     (first))))

@vpetruchok
Copy link

vpetruchok commented Nov 3, 2020

(defn most-frequent [coll]
  (if (empty? coll)
    nil
    (let [freqs (reduce (fn [m k] (update m k (fnil inc 0))) {} coll)
          max-entry (apply max-key second freqs)]
      (key max-entry))))

@nxvipin
Copy link

nxvipin commented Nov 3, 2020

(defn most-frequent [coll]
  (some->> (seq coll)                               ;; Short circuit immediately if the collection is empty
           (reduce #(update %1 %2 (fnil inc 0)) {}) ;; Make a map of element -> frequency
           (apply max-key val)                      ;; Find the map entry with the greatest frequency
           first))                                  ;; Return the element

@RedPenguin101
Copy link

RedPenguin101 commented Nov 3, 2020

(defn most-frequent [xs]
  (->> xs
       (group-by identity)
       (sort-by #(count (second %)))
       last
       first))

@diavoletto76
Copy link

diavoletto76 commented Nov 3, 2020

(defn most-frequent [xs]
  (->> (sort xs)
       (partition-by identity)
       (sort-by count)
       (last)
       (last)))

@PEZ
Copy link

PEZ commented Nov 3, 2020

(defn most-frequent [coll]
  (some->> coll
           (group-by identity)
           vals
           (sort-by count #(> %1 %2))
           first
           first))

(comment
  (most-frequent [2 2 3 4 4 2 1 1 3 2]) ;=> 2
  (most-frequent []) ;=> nil
  (most-frequent [1 1 4 4 5]) ;=> 1
  (most-frequent [1 "a" "a" :foo :foo :foo 1 1 "a" #{1} "a"]) ;=> "a"
  )

@jumarko
Copy link

jumarko commented Nov 4, 2020

See https://github.com/jumarko/clojure-experiments/blob/master/src/clojure_experiments/purely_functional/puzzles/0402_most_frequent.clj#L6-L10

(defn most-frequent [coll]
  (when-not (empty? coll)
    (let [by-number (group-by identity coll)
          [num _occurences] (apply max-key (comp count val) by-number)]
      num)))

(deftest test-most-frequent
  (testing "empty collection"
    (is (nil? (most-frequent []))))
  (testing "non-empty collection"
    (is (= 2 (most-frequent [2 2 3 4 4 2 1 1 3 2])))
    (is (= 4 (most-frequent [1 1 4 4 5])))))

@germ13
Copy link

germ13 commented Nov 4, 2020

(defn most-frequent [elements]
  (if (= [] elements) nil
    (loop [el elements
           rsum (apply merge (map #(hash-map (keyword (str %)) 0) (set elements)))]
      (if (empty? el)
        (symbol (key (apply max-key val rsum)))

        (recur (rest el)
               (update-in rsum
                          [(keyword (str (first el)))]
                          inc))))))

@michelemendel
Copy link

michelemendel commented Nov 4, 2020

Note: Some of the answers won't work with mixed types when sorted, because of class cast exception.

For example:

[nil "hello" true nil]

@PEZ
Copy link

PEZ commented Nov 4, 2020

@michelemendel I noticed that we both went for group-by instead. 😄

@michelemendel
Copy link

michelemendel commented Nov 4, 2020

@PEZ Yes, I started with group-by, tried partition which needed sorting, and when this failed with examples from the edabit site I went back to the group-by.

@KingCode
Copy link

KingCode commented Nov 4, 2020

Works for mixed types as well:

(defn most-frequent [xs]
  (->> xs
       (partition-by identity)
       (group-by first) vals
       (map flatten)
       (sort-by (comp - count))
       ffirst))

More efficient if we combine the first four components into a single pass-through:

(defn most-frequent [xs]
  (->> xs
       (sequence (comp (partition-by identity)
                       (group-by first)
                       (map second)
                       (map flatten)))
       (sort-by (comp - count))
       ffirst))

@steffan-westcott
Copy link

steffan-westcott commented Nov 4, 2020

(defn most-frequent [xs]
  (->> xs (group-by identity) vals (sort-by (comp - count)) ffirst))

@KingCode
Copy link

KingCode commented Nov 4, 2020

@steffan-westcott Nice! Just the essentials :)

@souenzzo
Copy link

souenzzo commented Nov 4, 2020

Using transducers, just for fun!

(letfn [(xf-most-frequent ([rf]
                           (let [index (volatile! {})]
                             (fn
                               ([] (rf))
                               ([result]
                                (let [mf (first (last (sort-by val @index)))]
                                  (-> result
                                      (rf mf)
                                      rf)))
                               ([result el]
                                (vswap! index update el (fnil inc 0))
                                result)))))
        (most-frequent ([coll]
                        (-> xf-most-frequent
                            (sequence coll)
                            first)))]
  {:a (most-frequent [2 2 3 4 4 2 1 1 3 2])
   :b (most-frequent [])
   :c (most-frequent [1 1 4 4 5])})
=> {:a 2, :b nil, :c 4}

@steffan-westcott
Copy link

steffan-westcott commented Nov 4, 2020

A small tweak to my first effort to avoid the sort:

(defn most-frequent [xs]
  (some->> xs (group-by identity) vals (apply max-key count) first))

I'm sure our answers are anagrams of each other 😀

@proush42
Copy link

proush42 commented Nov 5, 2020

(defn most-frequent [coll]
  (let [freqs (reduce (fn [m x]
                        (assoc m x (inc (get m x 0))))
                      {}
                      coll)]
    (->> (sort-by second > freqs)
         ffirst)))

@PEZ
Copy link

PEZ commented Nov 5, 2020

I struggled a bit with how to unit-test this so I skipped that in my first submission. Here's a take on that that I'd like feedback on:

(defn most-frequent 
  {:test (fn []
           (are [accepted coll]
                (some #(= % (most-frequent coll)) accepted)
             [2]    [2 2 3 4 4 2 1 1 3 2]
             [nil]  []
             [1 4]  [1 1 4 4 5]
             [true] [nil "hello" true nil true true]))}
  [coll]
  (some->> coll
           (group-by identity)
           vals
           (sort-by count #(> %1 %2))
           first
           first))

@alex-gerdom
Copy link

alex-gerdom commented Nov 9, 2020

(defn most-frequent-stream
  "Lazy sequence of which element has occurred most often up through point in collection"
  ([xs] (most-freq-stream xs {}))
  ([xs counts] (most-freq-stream xs counts nil))
  ([xs counts mf]
   (lazy-seq
    (when (seq xs)
      (let [x (first xs)               ;; Will referencing head here be issue?
            xc (inc (or (counts x) 0)) ;; x count
            mc (or (counts mf) 0)      ;; max frequent val count
            nmf (if (< xc mc) mf x)]   ;; new most frequent val
        (cons nmf
              (most-freq-stream (rest xs) (assoc counts x xc) nmf)))))))

(defn most-frequent
  "Return most frequent element in coll. In event of a tie, return the first to hit that frequency"
  {:test #(do
            (assert (= (most-frequent [2 2 3 4 4 2 1 1 3 2]) 2)) ;=> 2
            (assert (nil? (most-frequent []))) ;=> nil
            (assert (= (most-frequent [1 1 4 4 5]) 4)))}
  [xs]
  (last (most-freq-stream xs)))

(test #'most-frequent)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment