[Freeciv-Dev] random shuffling (was: Two patches)

[Reinier Post <rp@xxxxxxxxxx>]

On Tue, Jul 25, 2000 at 11:25:24PM +1000, David Pfitzner wrote:
> > At 2000/06/28 16:28 , Kero van Gelder wrote:
> > >First patchs improves the shuffle_players() to perfect randomness (it
> > >was close, but n! is not a perfect divisor of n^n), save the
> > >randomness of my_rand().

[...]
  
>    for(i=0; i<game.nplayers; i++) {
> -    pos = myrand(game.nplayers);
> +    /* for each run: shuffled[ <i ] is already shuffled [Kero] */
> +    pos = game.nplayers - myrand(game.nplayers) - 1;
>      tmpplr = shuffled[i]; 
>      shuffled[i] = shuffled[pos];
>      shuffled[pos] = tmpplr;
> 
> I believe Kero has the right idea, and the current code is wrong,
> but Kero's implementation is off.

Yes, if myrand(x) uniformly produces an integer between 0 and x-1 inclusive,
this patch has no effect.  The correct line seems to be

  pos = game.nplayers - myrand(game.nplayers - i) - 1;

as explained to me by

  http://www.merlyn.demon.co.uk/pas-rand.htm#Shuf
  http://www.faqs.org/faqs/cryptography-faq/part08/
   # question 8.13

-- 
Reinier