From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.num-analysis
Subject: Re: randomization of a bitmap by in-place swap
Date: 4 Oct 1995 18:26:23 GMT

In article <rl3sDFx2tA.LsG@netcom.com>,
Zeus Paleologos <rl3s@netcom.com> wrote:
>My cousin has developed an algorithm that randomizes a bitmap by repeatedly
>selecting two points in the 2-D array at random and swapping their values.
>Can someone suggest a mathematical model that he can use to predict the
>degree of disorder (that is, change from the original configuration) of 
>an 'm' x 'n' array after 's' swaps?  Is there a way to approximate at
>what point swapping produces no additional disorder?  What changes
>would be needed to modify the model for 3-D arrays or even n-D arrays?

In article <44ucod$ts9@bubba.ucc.okstate.edu>,
John Chandler <jpc@a.cs.okstate.edu> responded:
>Apply the shuffling algorithm of R. Durstenfeld to the rows.
>This requires only a finite number of swaps, and completely
>randomizes the order of the rows.
>Then apply the algorithm to the columns.
>This randomizes the order of the columns.
>Presumably the entire matrix is now as random as you can get it.

I have to disagree. You have in this way achieved one of the (n!)*(m!)
possible permutations in  S_n x S_m, which in practice may be just fine,
but you have only considered a fraction of the  (n*m)! permutations in
S_{n*m}. If, for example, you use your algorithm to shuffle the entries
of a square matrix, you'll create many more matrices, but all with
the same determinant (up to sign), a condition which will not be true
of all permutations of the  n^2  elements.

You could, of course, use any shuffling algorithm on the full set of
n*m points, treating them as a single long linear array.

Among the references to measures of disorder would have to be the works
of Persi Diaconis, who has made a long (and entertaining) study of
card shuffling and related phenomena.

dave