Shuffle generation

[Richard Tobin]

[What the #$%^* is it that puts "Followup-to: poster" on articles???]

In article <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric at snark.thyrsus.com> eric at snark.thyrsus.com (Eric S. Raymond) writes:
>In one of my programs, I have a requirement to generate random shuffles
>of arbitrary size.

Swap each element of the array, in order, with a random later-or-same
element of the array, eg

  for(i=0; i<n; i++)
  {
    int j, t;

    j = i + random() % (n-i);

    t = a[i]; a[i] = a[j]; a[j] = t;
  }

This essentially chooses a random element for the first position, then
a random one of those remaining for the second position, and so on.

Note that swapping each element with a random element chosen from the
whole array (ie j = random() % n) doesn't give you a perfectly uniform
distribution.

> Replies by email, please.

This is a common request, so I'm posting.

-- Richard
-- 
Richard Tobin,                       JANET: R.Tobin at uk.ac.ed             
AI Applications Institute,           ARPA:  R.Tobin%uk.ac.ed at nsfnet-relay.ac.uk
Edinburgh University.                UUCP:  ...!ukc!ed.ac.uk!R.Tobin