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 , Zeus Paleologos 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 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