[plt-scheme] please help with generating random permutation

On Thu, Sep 10, 2009 at 1:31 PM, keydana at gmx.de <keydana at gmx.de> wrote:

> Hi YC, hi Will,
>
> YC, I will try out the vyzo/crypto package thanks to your hint. I also
> wondered if I should use random-source-randomize!  from SRFI-27. There is
> also an example in the docs for generating random permutations, which I
> could possibly use. Would you recommend trying this?
>

I've not used srfi27 so I do not know much about it.  My usage of random
number are all crypto related and hence I am more familiar with vyzo/crypto,
which interfaces with libcrypto.

With high enough quality random seed and a good prng algorithm, you can be
reasonably certain the distribution will be statistically uniform given
enough runs.  .


> Regarding the point about drawing single cards, my concept (and the whole
> idea in the beginning quite some time ago...) was in fact to use amb, and I
> only added the "pre-shuffling" later when I realized that if I don't have
> enough constraints, amb will always choose the same person... Perhaps the
> initial idea about amb was not so good after all. Only now I think I won't
> have the time to rework the whole "algorithm" until the colleague gets
> impatient :-;
> Anyway, from your suggestion about serializing the state between runs of
> the script it occurred to me that perhaps I don't need the pre-shuffle at
> all. I could just rotate the list at every run and serialize it - then at
> least it would be "fair".
>

It all comes down to your requirement.  If your goal is to make every draw
independent, even if the same person can be drawn multiple times in a row,
then you just need to feed the list through a true random number generator.

But if you need more controlled output - i.e. every person who has
previously been drawn should not be draw again until all of the people have
been drawn at least once, etc., then you will have to account for the
constraints in your design.  This is "less" not "more" random.  The only
randomness I heard was that the same person should not "always work on
Mondays".  To make sure that's the case - just exclude the person who has
previously been drawn to Mondays from the next round of drawing.

>From fair to all perspective, simluating drawing cards will do the trick, as
each card drawn will not be put into the deck until no cards are left - this
way everyone gets a turn before someone has to do it twice.  This is
basically the same as asking everyone to draw from a hat.

This is doable even without randomness - order people into a list, have them
go through a round, then shift the list by N day so their next round will
start on the "next day of the week" from their previous assignments.

Hope this helps,
yc
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090910/e03631c1/attachment.html>