Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23
Jim Gillogly (jim@acm.org)
Fri, 30 Oct 1998 09:04:39 -0800
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
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:15:23