Xref: utzoo sci.math:17383 comp.lang.c:39259
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!ub!uhura.cc.rochester.edu!rochester!pt.cs.cmu.edu!o.gp.cs.cmu.edu!andrew.cmu.edu!dd2i+
From: dd2i+@andrew.cmu.edu (Douglas Michael DeCarlo)
Newsgroups: sci.math,comp.lang.c
Subject: Re: Shuffle generation
Message-ID: <8c=sAju00Vp_Ihxl4r@andrew.cmu.edu>
Date: 14 May 91 06:26:55 GMT
References: <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric@snark.thyrsus.com>
Organization: Electrical and Comp. Engineering, Carnegie Mellon, Pittsburgh, PA
Lines: 22
In-Reply-To: <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric@snark.thyrsus.com>

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.  I am using the obvious method, as follows:
> .....
> .....
> 1) Is there a known way of choosing a formula for TRANSPOSITIONS(n) to
>   guarantee random mixing in some a priori sense?
>
>2) This is, obviously, a naive method.  Is there a `smart' algorithm that
>   works better?

To swap N items in an array A[0..(n-1)], the following O(N) algorithm works:

for (i=0; i < N; i++) {
     swap(i, i + random(N - i));
}

Where random(r) is a function which returns a random integer in 0..(r-1)
and swap(a, b) swaps the stuff in array A[a] with A[b].

- Doug