[Fluxus] picking a function with weights

[Matt Jadud]

Hi Gabor,

On Tue, Feb 2, 2010 at 9:34 AM, gabor papp <gabor.lists at mndl.hu> wrote:
>> I generally do weighting by duplicating list elements, but there must be
>> a better way?
>
> i would do it with an associative list like this. maybe there's even a
> better way.

You beat me to it.

I used an association list to assign weights. The chooser function
sums the weights, so that you don't have to worry about summing them
to 1.0 yourself. It picks a random value in the appropriate range, and
then walks the association list until it finds the correctly weighted
item (I think).

The distribution tester seems to produce sensible values. That is, for
my test list, it says:

#hash((common . 2312) (popular . 4603) (rare . 951) (alsocommon . 2134))

which says that "popular" is twice as frequent as "comman" and
"alsocommon", and five times as frequent as "rare". Of course, I wrote
no contracts, no tests, and would say that it is up to the diligent
programmer to make sure this does what they want. :)

It felt good to write even a few lines of Scheme... it's been too long...

Cheers,
Matt

#lang scheme

(define wl `((popular 10)
             (common 5)
             (alsocommon 5)
             (rare 2)))

(define (chooser wl choice runsum prev)
  (cond
    [(empty? wl) (first prev)]
    [(> runsum choice)
     (first prev)]
    [else
     (chooser (rest wl)
              choice
              (+ (second (first wl)) runsum)
              (first wl))]))

(define (weighted-choice wl)
  (let* ([max (apply + (map cadr wl))]
         [choice (random max)])
    (chooser wl choice 0 'error)))

(define (test-dist)
  (let* ([h (make-hash)])
    (let loop ([n 10000])
      (unless (zero? n)
        (let ([c (weighted-choice wl)])
          (hash-set! h c
                     (add1 (hash-ref h c (lambda () 0)))))
        (loop (sub1 n))))
    (printf "~a~n" h)))