[104883] in Cypherpunks
Re: Random array
daemon@ATHENA.MIT.EDU (Jim Gillogly)
Fri Oct 30 14:04:43 1998
Date: Fri, 30 Oct 1998 08:44:53 -0800
From: Jim Gillogly <jim@acm.org>
To: Coderpunks <coderpunks@toad.com>
Reply-To: Jim Gillogly <jim@acm.org>
I said:
> >for j from 255 down to 1
> > pick random number k from 0 through j
> > swap items j and k
Jesus Cea Avion responded:
> I'd rather prefer
>
> for i in 1..n
> j = random(1..n)
> swap(a[i],a[j])
>
> So, each position has equal posibilities. Since random+random=random
> :-), each cell is visited one time, and the element placed there is
> random and taken from the entire set, the final array will be random.
I'm glad you suggested this one, because I hadn't ever gotten around to
doing the cases. Let's look at the one I posted first, with three
elements abc. 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 cba 1/6 bac 1/6
cba 1/6 abc 1/6 abc 1/6
This is the desired result: equal probabilities for the 6 possible
permutations. Now let's look at your algorithm. After the first
iteration, we have:
abc 1/3 bac 1/3 cba 1/3
After the second iteration, each of the following has probability 1/9:
bac abc acb abc bac bca abc cab cba
After the third iteration, each of the following has probability 1/27:
cab cba bca cba cab acb cba bac abc
bca acb abc acb bca bac acb cba cab
bac abc acb abc bac bca abc cab cba
So the six possible permutations of abc have this probability:
abc: 5/27
acb: 5/27
bac: 4/27
bca: 4/27
cab: 4/27
cba: 5/27
This is a subtle effect and wouldn't be noticeable for 256 elements,
but it would not in fact result in even probabilities for all sizes.
May as well (a) save an iteration; and (b) get the right answer.
As Greg Rose suggests, it is very common to stuff this up.
Please God don't let this mutate into the Monty Hall argument!
--
Jim Gillogly
Trewesday, 9 Blotmath S.R. 1998, 16:26
12.19.5.11.12, 10 Eb 5 Zac, Seventh Lord of Night
