Instantly share code, notes, and snippets.

# ericnormand/00 Index map.md

Created March 15, 2021 13:47
Show Gist options
• 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.

### Sinha-Ujjawal commented Mar 16, 2021 • edited

(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 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 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 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 commented Mar 18, 2021 • edited

@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 commented Mar 22, 2021 • edited

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

### prairie-guy commented Apr 3, 2021 • edited

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