[104886] in Cypherpunks
Re: Random array
daemon@ATHENA.MIT.EDU (Jim Gillogly)
Fri Oct 30 14:16:14 1998
Date: Fri, 30 Oct 1998 09:04:39 -0800
From: Jim Gillogly <jim@acm.org>
To: Coderpunks <coderpunks@toad.com>
Reply-To: Jim Gillogly <jim@acm.org>
Yes, I stuffed up the example of the first algorithm. The conclusion
is right, but I lost focus enumerating the second second column of the
second iteration:
> >for j from 255 down to 1
> > pick random number k from 0 through j
> > swap items j and k
After the first iteration we have three possibilities
with equal probability 1/3:
cba 1/3 acb 1/3 abc 1/3
On the second iteration, the third element is constant, but the first
two have an equal probability of getting swapped:
bca 1/6 cab 1/6 bac 1/6
cba 1/6 acb 1/6 abc 1/6
As I said earlier, Sr. Avion's algorithm ends up with equal
probabilities of 1/27 at the leaf nodes, and there's no way
to divide this into 6 target permutations evenly.
--
Jim Gillogly
Trewesday, 9 Blotmath S.R. 1998, 17:00
12.19.5.11.12, 10 Eb 5 Zac, Seventh Lord of Night
