Skip to content

Instantly share code, notes, and snippets.

@ericnormand
Created March 15, 2021 13:47
  • 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/f38b0ecda60ebe51b1ac4395b8db3b6a to your computer and use it in GitHub Desktop.

Index map

A vector can be seen as a mapping of index to value. However, we want a mapping from value to indexes. Write a function that takes a sequence and returns a map where the elements of the sequence are the keys and the values are sets of the indexes where the value is found.

Examples

(index-map []) ;=> {}
(index-map [1 2 3]) ;=> {1 #{0} 2 #{1} 3 #{2}}
(index-map [1 1 1]) ;=> {1 #{0 1 2}}
(index-map [1 2 1 2 1]) ;=> {1 #{0 2 4} 2 #{1 3}}

Bonus: Write the inverse function that takes one of the returned maps and turns it into a sequence.

Thanks to this site for the challenge idea where it is considered Hard in Ruby. The problem has been modified from the original.

Please submit your solutions as comments on this gist.

@vpetruchok
Copy link

(defn index-map [coll]
  (->> coll
       (map vector (range))
       (reduce (fn [acc [idx elem]]
                 (let [indexes (get acc elem #{})]
                   (assoc acc elem (conj indexes idx))))
               {})))
(defn index-map2coll [m]
  (->> m
       (mapcat (fn [[k idxs]]
                 (for [idx idxs]
                   [k idx])
                 ))
       (sort-by second)
       (mapv first)))

@proush42
Copy link

proush42 commented Mar 18, 2021

@nwjsmith

(defn index-map
  [coll]
  (reduce-kv (fn [m i x] (update m x (fnil conj #{}) i))
             {}
             coll))

(defn un-index-map
  [m]
  (->> m
       (mapcat (fn [[x is]] (map #(vector % x) is)))
       (sort-by first)
       (map second)
       (into [])))

You can use "mapv" to generate a vector result, eliminating the need for "(into [])"

@vmpj
Copy link

vmpj commented Mar 22, 2021

(defn index-map [v]
  (reduce-kv (fn [r k v] 
               (->> (conj (get r v #{}) k)
                    (assoc r v)))
             {}
             v))

@prairie-guy
Copy link

prairie-guy commented Apr 3, 2021

(use '[clojure.set :only (union)])

(defn index-map [s]
  (->>
   (map-indexed vector s)
   (map (fn [s] {(s 1) (set [(s 0)])}))
   (apply (partial merge-with union))))

(defn map-index [idx-map]                                                                                                                             
  (let [im (fn [[k v]] (map (fn [vv] [vv k]) v))]                                                                                                     
    (->> (map im idx-map)                                                                                                                             
         (flatten)                                                                                                                                    
         (partition 2)                                                                                                                                
         (sort-by first)                                                                                                                              
         (map second)                                                                                                                                 
         (vec))))

@sim-f
Copy link

sim-f commented Apr 7, 2021

(defn index-map [v]
  (let [m (zipmap (distinct v) (repeat #{}))
        c (count v)]
    (reduce
     (fn [m index]
       (update m (get v index) #(conj % index)))
     m
     (range 0 c))))

(defn index-map->vec [imap]
  (->> imap
       (reduce
        (fn [smap index-map]
          (->> index-map
               (apply (fn [n is] (map (fn [i] [i n]) is)))
               (into smap)))
        (sorted-map))
       vals
       vec))

@s3dse
Copy link

s3dse commented Apr 11, 2021

(defn index-map [xs]
  (reduce-kv
    (fn [m k v]
      (merge-with into m {v (into (sorted-set) [k])}))
    {}
    xs))

(defn index-map->vec [m]
  (mapv first
        (reduce-kv
          (fn [r k v]
            (->> (map #(vector k %) v)
                 (apply conj r)
                 (sort-by second)))
          [] m)))

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