On 17/05/2008, Joel Miller <[EMAIL PROTECTED]> 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. _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor