weighted-shuffle-fancy.clj

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