Re: updated load balancing qmail-qmqpc.c mods

[Pavel Kankovsky]

On 2 Aug 2000, Frank D. Cringle wrote:

> Generating a random permutation algorithmically is not too easy.

Oh really?

  int i, j, x;
  int a[N];

  for (i = 0; i < N; ++i)
    a[i] = i;
  for (i = N - 1; i > 0; --i) {
    j = random(i);
    x = a[i]; a[i] = a[j]; a[j] = x;
  }

where random(i) is a "good enough" PRNG generating an integer between
0 and i - 1 with the uniform distribution. The result is in a[].

The proof of correctness (i.e. that the aformentioned piece of code
generates a pseudorandomly chosen permutation of (0, ..., N-1) with
the uniform distribution) is left as an exercise for the reader.

--Pavel Kankovsky aka Peak  [ Boycott Microsoft--http://www.vcnet.com/bms ]
"Resistance is futile. Open your source code and prepare for assimilation."