418 - https://PurelyFunctional.tv/newsletter

00 Index map.md

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.

@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 [])"

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

(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))))

(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))

(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)))