[Tutor] quickly pulling marbles out of urns

[John Fouhy]

On 17/05/2008, Joel Miller <joel.c.miller at gmail.com> wrote:
>  I have an urn with many different colors of marbles in it.  I pull one
>  out and note the color.  I do not replace it.

Kent's suggest seems simplest: represent the marbles as a list of
integers, where marbles[i] is the integer corresponding to marble i's
colour.

If that doesn't work (too many marbles?), maybe some kind of binary
tree approach?  e.g. a MarbleColour class which stores
 - the colour
 - the number of marbles with this colour
 - the number of marbles in the left subtree
 - the number of marbles in the right subtree

where either subtree could be None (and thus have 0 marbles).

Set the binary tree up initially so it's balanced by marble weight (if
the marble colours are all approximately the same size at the start,
you could approximate this by just filling in colours from the top in
any order).  Then you can randomly generate a colour by generating a
random int in (0,1) and comparing with the proportions in the node.
Then you just have to update the weights for the colour you choose and
all nodes above it.

Should be log_2(n) to pick one colour and n.log_2(n) to pick colours
until you run out.

-- 
John.