From: Chris Pine <nemo@...>
Date: 2003-04-22T05:29:14+09:00
Subject: Re: Biased weighted random?

----- Original Message -----
From: "Hal E. Fulton" <hal9000@hypermetrics.com>

Well, I guess the problems are related. I see
a shuffle as being a sequence of a specific (as
opposed to an arbitrary) length. Unless I'm
missing something.
----------------------------

As I understand it, `shuffle' refers to reordering a fixed number of
objects; in other words, it's a permutation.

If you shuffle a deck of cards, you don't expect to see the 4 of Hearts more
(or less) than once.

I thought your original question related to assigning a weight to various
objects and generating a sequence with as little "local repetition" as
possible, but with long-term repetition as a guarantee.

In a shuffle, you would not have weights, just objects.  If you wanted 7
aces to come out of your shuffle, you would have to put 7 aces in your
original deck.

Of course, if you wanted to, you could duplicate (or triplicate, or
whatever)) your objects according to their weights, then shuffle, read the
new order to the end, then shuffle again... you might get repetition in
between shuffles, though.  If you reject such shuffles (reshuffling in such
instances), that would be a decent algorithm, I guess... better than the
transition matrix algorithm, I think, but not quite as nice as my other one
(if you don't mind my saying so :).  It wouldn't always work, and you might
run into infinite-reshuffling-loops in those instances.


Chris