Received: by 10.236.139.199 with SMTP id c47mr1423360yhj.5.1331693947007;
        Tue, 13 Mar 2012 19:59:07 -0700 (PDT)
X-BeenThere: scala-melb@googlegroups.com
Received: by 10.236.16.39 with SMTP id g27ls104386yhg.9.gmail; Tue, 13 Mar
 2012 19:59:06 -0700 (PDT)
Received: by 10.236.192.164 with SMTP id i24mr1391983yhn.8.1331693946361;
        Tue, 13 Mar 2012 19:59:06 -0700 (PDT)
Received: by 10.236.192.164 with SMTP id i24mr1391982yhn.8.1331693946350;
        Tue, 13 Mar 2012 19:59:06 -0700 (PDT)
Return-Path: <t...@dryft.net>
Received: from mail-gx0-f180.google.com (mail-gx0-f180.google.com [209.85.161.180])
        by gmr-mx.google.com with ESMTPS id t62si1392419yhj.2.2012.03.13.19.59.06
        (version=TLSv1/SSLv3 cipher=OTHER);
        Tue, 13 Mar 2012 19:59:06 -0700 (PDT)
Received-SPF: pass (google.com: domain of t...@dryft.net designates 209.85.161.180 as permitted sender) client-ip=209.85.161.180;
Authentication-Results: gmr-mx.google.com; spf=pass (google.com: domain of t...@dryft.net designates 209.85.161.180 as permitted sender) smtp.mail=t...@dryft.net
Received: by gglu1 with SMTP id u1so1955789ggl.39
        for <scala-melb@googlegroups.com>; Tue, 13 Mar 2012 19:59:06 -0700 (PDT)
        d=google.com; s=20120113;
        h=mime-version:in-reply-to:references:date:message-id:subject:from:to
         :content-type:x-gm-message-state;
        bh=cR1DfDUSKSVTj8LvLwl2LK96+RtWDYQb80/f1WZLgy0=;
        b=mgggaPEi8ubEtnYLjNM5i838uobQDzvUNc0jrOvuyLOBWPYeqnX9G3ogYG4W+c3B2H
         tkrNWqSI+Lub+bH2dczEBg0mBpReMpwkzo+99ll3umAKz+ZJ/Ulcun0xoqzFR1EE4GnG
         YLuOCAPe+rXm6TFXSXa+pva8b5tBXPgMah34SKPmOMIEJ/GQq+zpBpvb0mZfZ6DF74Z3
         u/+E0fmAVo9bPAN7gtdWk2cPgjHgsw1l3bQtqLBqdGs7sP9KnsXSmd9YcXWUba5aIL0v
         6xujdojzM5fMy8jH0fGRJCFw1T6vRHI/MotfrdUO6jf3NYhyGtWFQ3pVsS2SJGDs5eBo
         B6RQ==
MIME-Version: 1.0
Received: by 10.224.87.76 with SMTP id v12mr1379584qal.12.1331693945952; Tue,
 13 Mar 2012 19:59:05 -0700 (PDT)
Received: by 10.229.135.78 with HTTP; Tue, 13 Mar 2012 19:59:05 -0700 (PDT)
In-Reply-To: <CAGJkGJ91SfWXejCUOy-NdKkOmVTQhNq=kaFWkjJZGP3HkuV...@mail.gmail.com>
References: <CAGJkGJ91SfWXejCUOy-NdKkOmVTQhNq=kaFWkjJZGP3HkuV...@mail.gmail.com>
Date: Wed, 14 Mar 2012 13:59:05 +1100
Message-ID: <CABEgq967zJ+xUR_N9jjMMOiCpXqBGwBRp34Z_a+3cA7jQ+h...@mail.gmail.com>
Subject: Re: Another Scala problem: Weighted Random Selection
From: Toby Corkindale <t...@dryft.net>
To: scala-melb@googlegroups.com
Content-Type: text/plain; charset=UTF-8
X-Gm-Message-State: ALoCoQlh9idRkw7ckr2Pk22rvE/RQxFgbv1bJEez1/CQh0y7WTMZTQYNAF3Vrk7M9SOrznMNWkiI

On 9 March 2012 01:02, Ben Hutchison <brhutchi...@gmail.com> wrote:
> case class WeightedItem[T](item: T, weight: Double)
>
> def weightedSelection[T](items: Seq[WeightedItem[T]], numSelections:
> Int, r: Random): Seq[T] = ???
>
> Your task is to implement weightedSelection, such that it makes
> 'numSelections' random selections (with replacement) from 'items',
> where the probability of selecting each item is proportional to its
> weighting.


I wrote this solution before looking at any others:
https://gist.github.com/2033639
Was a fairly fast implementation, but didn't have time to refine it.

Looks like I went for the same concept as Jem, with spreading the
options out to occupy space in a range proportional to their weight,
then normalising the random number to that range to discover which
bucket to land it.

The ugliness in mine comes from the pick_one() method; I'm sure it
should be using one of the collections methods with an accumulator to
achieve the same result, somehow.

-Toby