(no subject)

Stephen Dennis (sdennis@svdltd.com)
Wed, 28 Oct 1998 16:56:15 -0800

• Next message: Alex Alten: "Re: Shuffling"
• Previous message: Anonymous: "Re: Java applet security, exportability, Jon Postel haiku"

If you are trying to make every element in the original array A equally
likely to occur in any position of the final array A, then your snippet
doesn't work ... regardless of SWAP_TIMES.

Try this instead:

#define NELEMENTS 256
A[NELEMENTS];

for (int i = 0; i < NELEMENTS-1; i++)
{
        for (int j = i+1; j < NELEMENTS; j++)
        {
                int x = getrand2(j)
                swap(A[i],A[x]);
        }
}

A crude getrand2 is:

#define getrand2(x) (getrand()%(x))

but that doesn't have a flat distribution unless the maximum range of
getrand() is divisable by (x+1)....blah blah blah.

Here's a better one:

int getrand2(int x)
{
        long n;
        if (x <= 0)
                return -1;
        do
        {
                n = random(); // returns an evenly-distributed
psuedo-random number on [0,LONG_MAX]
        } while (LONG_MAX - n < x);
        return (n % x);
}

-----Original Message-----
From: Anonymous [mailto:nobody@replay.com]
Sent: Wednesday, October 28, 1998 3:32 PM
To: CodherPlunks@toad.com
Subject:

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

• Next message: Alex Alten: "Re: Shuffling"
• Previous message: Anonymous: "Re: Java applet security, exportability, Jon Postel haiku"