enum-dist->buckets.clj

(defn ^:private enum-dist->buckets
  "Preprocessing phase of the Alias Algorithm

   Build a vector of bucket in O(N log N) complexity:
   - Input: a sequence of pairs [value associated-weighted]
   - Output: a vector of tuples [value-1 value-2 p1-over-p2]"
  [enum-dist]
  (let [bucket-nb (dec (count enum-dist))   ; Number of buckets to fill
        total-vol (sum-weights enum-dist)   ; Total volume split over the buckets
        bucket-vol (/ total-vol bucket-nb)] ; Volumne of each bucket
    (loop [to-verse (into (sorted-set)      ; Remaining quantity to verse in the buckets
                     (map (comp vec reverse))
                     enum-dist)
           buckets []]                      ; The filled buckets to return
      (if (<= 2 (count to-verse))           ; Filling one more bucket
        (let [[bucket to-verse] (fill-one-bucket to-verse bucket-vol)]
          (recur to-verse (conj buckets bucket)))
        buckets))))                         ; Return when nothing to verse