Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A sampling-based version of weighted-shuffle (better to use the exponential random solution)
;; This is asymptotically slower (n^2) than the exponential random sort
;; one (n log n) shown in https://gist.github.com/timmc/1211c1ac8ae96c2b42c94124005b5414
;; but it is preserved here for possible later interest
(defn weighted-random-sample
"Given a coll of weights, pick one according to a weighted-random
selection, and return its index. Weights must be non-negative."
[weights]
(when (empty? weights)
(throw (IllegalArgumentException. "Cannot sample from empty list")))
;; Pick a target somewhere between zero and the sum of the weights
(let [total (apply + weights)
target (* total (rand))]
;; Walk the list until the target is reached or passed
(loop [index 0
tail weights
accumulated 0]
(if (<= (count tail) 1)
;; If only one element left, return its index.
index
(let [next-accum (+ accumulated (first tail))]
(if (< target next-accum)
;; If we would pass the target by accumulating the current
;; weight, then this is the right index
index
;; Otherwise, move along
(recur (inc index)
(rest tail)
next-accum)))))))
(defn weighted-shuffle-annotated
"Perform a weighted shuffle on a collection of element/weight pairs."
[weighted-els]
(lazy-seq
(if (empty? weighted-els)
[]
(let [picked-index (weighted-random-sample (map second weighted-els))
picked-pair (nth weighted-els picked-index)]
(cons picked-pair (weighted-shuffle-annotated
(concat (take picked-index weighted-els)
(drop (inc picked-index) weighted-els))))))))
(defn weighted-shuffle
"Perform a weighted shuffle on a collection. weight-fn is called at
most once for every element in the collection."
[weight-fn coll]
(->> coll
(shuffle) ;; tie-break any zero weights
(map (juxt identity weight-fn))
(weighted-shuffle-annotated)
(map first)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.