Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

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.

@steffan-westcott
Copy link

steffan-westcott commented Mar 15, 2021

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

(defn invert-index-map [m]
  (vals (reduce-kv (fn [m' x idxs] (merge m' (zipmap idxs (repeat x)))) (sorted-map) m)))

@tvirolai
Copy link

tvirolai commented Mar 15, 2021

(require '[clojure.set :refer [union]])

(defn index-map [s]
  (reduce-kv (fn [acc index val]
               (merge-with union
                           acc
                           {val #{index}}))
             {}
             s))

(defn map-index [m]
  (let [vals-indexes (reduce-kv (fn [acc index val]
                                  (into acc
                                        (for [v val]
                                          [v index])))
                                {} m)]
    (mapv (partial get vals-indexes) (range (count vals-indexes)))))

@daniel-quintoandar
Copy link

daniel-quintoandar commented Mar 15, 2021

(defn index-map [coll]
  (transduce
   (map-indexed list)
   (completing
    (fn [m [i e]]
      (update m e (fnil conj #{}) i)))
   {}
   coll))

@proush42
Copy link

proush42 commented Mar 15, 2021

(defn index-map [coll]
  (reduce (fn [m [idx x]]
            (update-in m [x] (fnil conj #{}) idx))
          {}
          (map-indexed vector coll)))

(defn rev-index-map [m]
  (let [elem->tups (fn [[x idxs]] (map #(vector % x) idxs))]
    (->> (mapcat elem->tups m)
         (sort-by first)
         (map second))))

@filippocostalli
Copy link

filippocostalli commented Mar 15, 2021

(defn occur [coll p]
  {p
    (loop [result #{} par coll counter 0]
      (if (= 0 (count par))
        result
        (recur
          (if  (= (first par) p)
             (conj result counter)
             result)
          (rest par)
          (+ 1 counter))))})

(defn index-map [s]
  (->> (distinct s)
       (map #(partial (occur s %)))
       (into (sorted-map))))

@nwjsmith
Copy link

nwjsmith commented Mar 15, 2021

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

@diavoletto76
Copy link

diavoletto76 commented Mar 15, 2021

(defn index-map [xs]
  (->> (map-indexed list xs)
       (group-by second)
       (map (fn [[a b]] (vector a (into #{} (map first b)))))
       (into {})))

(defn un-index-map [xs]
  (->> (map identity xs)
       (mapcat (fn [[a b]] (map #(list a %) b)))
       (sort-by second)
       (mapv first)))

@miner
Copy link

miner commented Mar 15, 2021

(defn index-map [coll]
  (persistent!
   (reduce-kv (fn [tm i k] (assoc! tm k (conj (get tm k #{}) i)))
              (transient {})
              (vec coll))))

(defn inv-index-map [m]
  (-> (reduce-kv (fn [sm k is] (reduce (fn [sm i] (assoc sm i k)) sm is))
                 (sorted-map)
                 m)
      vals
      vec))

@mchampine
Copy link

mchampine commented Mar 16, 2021

(defn index-map [s]
  (into {} (for [[k v] (group-by second (map-indexed vector s))] [k (set (map first v))])))

(defn un-index-map [m]
  (mapv first (sort-by second (apply concat (for [[k v] m] (map vector (repeat k) v))))))

@Sinha-Ujjawal
Copy link

Sinha-Ujjawal commented Mar 16, 2021

(defn index-map [coll]
    (reduce
        (fn [m [x i]] 
            (assoc m x (conj (get m x (sorted-set)) i)))
        {}
        (map-indexed (fn [i x] [x i]) coll)))
    
(defn index-map-inverse [m]
    (vals
        (reduce
            (fn [m [x is]]
                (reduce (fn [m i] (assoc m i x)) m is)) (sorted-map) m)))

Here's my solution. Please let me know if it's efficient. Also I am new to Clojure, so my vocabulary is pretty limited.

@arthurulacerda
Copy link

arthurulacerda commented Mar 16, 2021

(require '[clojure.set :as sets])

(defn index-map
  [arr]
  (reduce (fn [acc val] 
            (update acc 
                    (first (keys val)) 
                    #(sets/union %1 %2) 
                    (first (vals val))))
          {}
          (map-indexed #(hash-map %2 #{%1}) arr)))

(defn index-map-reverse
  [h-map]
  (map #(first %)
       (reduce-kv (fn [m k v]
                    (sort-by last (concat m (map #(vector k %) v))))
                  []
                  h-map)))

@sztamas
Copy link

sztamas commented Mar 17, 2021

(defn index-map [col]
   (->> col
        (map-indexed vector)
        (reduce (fn [m [idx x]] 
                  (update m x (fnil conj #{}) idx)) {})))


(defn indexed-map->seq [idx-map]
   (->> idx-map
        (reduce (fn [m [x idxs]]
                  (merge m
                         (zipmap idxs (repeat x))))
                (sorted-map))
        vals))

@vpetruchok
Copy link

vpetruchok commented Mar 18, 2021

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

@simbiotiqu
Copy link

simbiotiqu 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