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.

### 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 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 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 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 commented Mar 15, 2021 • edited

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

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