Shuffle generation

[Douglas Michael DeCarlo]

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.  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