[Freeciv-Dev] Re: Two patches

[David Pfitzner <dwp@xxxxxxxxxxxxxx>]

Jeff Mallatt <jjm@xxxxxxxxxxxx> 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().
> 
> I don't understand this patch.  The new code seems to me to have the same
> effect as the old code.

Patch was:

diff -ru freeciv/server/civserver.c dev/server/civserver.c
--- freeciv/server/civserver.c  Sun Jun 25 12:26:37 2000
+++ dev/server/civserver.c      Wed Jun 28 20:31:24 2000
@@ -844,7 +844,8 @@
   }
 
   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.  Patch should be: (untested)

-  for(i=0; i<game.nplayers; i++) {
+  for(i=0; i<game.nplayers-1; i++) {
-    pos = myrand(game.nplayers);
+    /* for each run: shuffled[ <i ] is already shuffled [Kero+dwp] */
+    pos = i + myrand(game.nplayers-i);

That is:
- current code goes to each index, and chooses random one from 
  all indicies;
- new code goes to each index (except last), and chooses random 
  one from remaining ones (ie, this index and higher indices).

The difference is subtle but there.  To elicidate Kero's explanation,
consider the case where nplayers==3.  With old code, get
  rand(3)*rand(3)*rand(3) = 27 equally likely outcomes, many of which 
are diplicate orderings.  In fact there are only 6 unique orderings.
Since 6 does not go into 27, these six orderings cannot be equally
likely.  QED.  (Well, that shows the old method is wrong; the proof 
that the new method is right is left as an exercise ;-)

-- David,  BSc etc...