Skip to content

Instantly share code, notes, and snippets.

@ericnormand
Created November 3, 2020 15:17
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save ericnormand/7944c8806ba447a7bee6301a168ecdcb to your computer and use it in GitHub Desktop.
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.

@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

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

@diavoletto76
Copy link

(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

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

@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

(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