1

Possible Duplicate:
What distribution do you get from this broken random shuffle?

This is from Skiena's Algorithm Design Manual.

Assume that myrand(a, b) generates a random number between a and b inclusive.

The following code generates permutations uniformly at random

for(int i = 0; i < n; i++)
    swap( a[i], a[myrand(i, n-1)]);

whereas the following doesn't.

for(int i = 0; i < n; i++)
    swap( a[i], a[myrand(0, n-1)]);

The question is, why?

Community
  • 1
  • 1
ARV
  • 6,287
  • 11
  • 31
  • 41
  • 2
    Are you sure it's supposed to generate permutations? It looks like it's shuffling the array (it looks like the Fisher-Yates shuffle). –  Jul 31 '11 at 15:29
  • 1
    A shuffled array is a permutation of that array. – Mat Jul 31 '11 at 15:32
  • @Mat: Well, yes, but only a single permutation. "Generate permutations" is more general (and harder). –  Jul 31 '11 at 15:33
  • @delnan: if you call it more than once it generates permutations at random. I don't think it's unusual to say for example that the function `socket` "creates sockets", although of course each call to it only creates one socket. You wouldn't *document* it "creates sockets", but informally that's what the function does (as opposed to what a single call to the function does). – Steve Jessop Jul 31 '11 at 15:38

1 Answers1

2

In the first case there are exactly n! possible paths for execution of the function (first rand has n possibilities, the second has n-1 ...). Since each of the n! possible permutations correspojnds to exactly one of these, they are uniformly distributed.

In the second case, there are n^n possible paths of distribution (n possible chioces the first time, n the second...). This does not map uniformly to the permutations so the distribution is uneven.

To check it out "by hand", generate all possibilities for a small n, like 3

numbers chosen  generated permutation
(0,0,0)         (2,0,1)
...              ...
hugomg
  • 68,213
  • 24
  • 160
  • 246
  • True mathematically, but not even the first algorithm can actually produce all permutations in practice. Note that pseudo-random number generators maintain a finite state (eg, a seed), and thus RNGs are necessarily doomed to start repeating "random" numbers after 2^b calls where b is the number of bits of state maintained by the RNG. Since b is fixed, and n! grows super-exponentially, there are more possible permutations of sequences of length n for even moderately sized n than there are RNG states for even the largest b used in practice, so RNGs cannot possibly produce every permumation. – Nicu Stiurca Apr 04 '12 at 02:48