[104832] in Cypherpunks
Re: Random array
daemon@ATHENA.MIT.EDU (Anonymous)
Thu Oct 29 13:40:29 1998
Date: Thu, 29 Oct 1998 17:33:29 +0100
From: Anonymous <nobody@replay.com>
To: coderpunks@toad.com
Reply-To: Anonymous <nobody@replay.com>
A couple responders have said there is no SWAP_TIMES
which would work. But I don't understand why the
following wouldn't work:
First of all, make sure that x and y can't be equal, since
there's no point in swapping an element with itself. This
should add a negligible amount of time.
x=getrand();
do
y=getrand();
while (x == y);
Now, simply calculate how many SWAP_TIMES it would take for it
to be equally as likely that an element would not be touched as
it would to land in its original spot.
(255/256)^(t*2) = 1/256
or
t = ln(1/256)/(2*ln(255/256))
or
708.3955
Another anonymous wrote:
In the following snippet of pseudo-code, what should the value of
SWAP_TIMES be to make the array A[] random, assuming
that getrand() returned a truly random integer between
0 and 255
A[256];
for(i=0;i<SWAP_TIMES;i++){
x=getrand();
y=getrand();
swap(A[x],A[y]);
}
Thanks
