Xref: utzoo sci.math:17450 comp.lang.c:39325
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!crdgw1!uunet!mcsun!ukc!edcastle!aiai!richard
From: richard@aiai.ed.ac.uk (Richard Tobin)
Newsgroups: sci.math,comp.lang.c
Subject: Re: Shuffle generation
Message-ID: <4722@skye.ed.ac.uk>
Date: 16 May 91 13:40:54 GMT
References: <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric@snark.thyrsus.com>
Reply-To: richard@aiai.UUCP (Richard Tobin)
Organization: AIAI, University of Edinburgh, Scotland
Lines: 34

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

In article <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric@snark.thyrsus.com> eric@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@uk.ac.ed             
AI Applications Institute,           ARPA:  R.Tobin%uk.ac.ed@nsfnet-relay.ac.uk
Edinburgh University.                UUCP:  ...!ukc!ed.ac.uk!R.Tobin