Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
(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 (fn [el]
;; Bound the weight to positive values
(let [weight (Math/max Double/MIN_VALUE (double (weight-fn el)))
;; Weighted Random Sampling (2005; Efraimidis, Spirakis)
;; http://utopia.duth.gr/~pefraimi/research/data/2007EncOfAlg.pdf
key (- (Math/pow (rand) (/ 1 weight)))]
[el key])))
(sort-by second)
(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.