Improving array shuffle

After reading an essay by Mike Bostock on the dangers of shuffling arrays in particular ways, I emulated his visualization in Excel.

I want to visualize whether a shuffle is truly random by visualizing the propensity for any given starting index to end up in another.

Here's what I came up with:

Please Login or Register  to view this content.

The problem is that I don't get what I expect, Fisher-Yates should show an even distribution (with a bit of noise). It doesn't.

What I don't know is whether this is a problem with my method (most likely), a problem with the shuffle (though I've tried a couple of Chip Pearsons implementations as well as my own - though they exhibit different behaviour), the way random numbers are generated in Excel or something else.

I've attached for perusal, would be good if someone could spot the error

So I'm getting a bit closer on a better shuffle, Chip's (from here http://www.cpearson.com/excel/ShuffleArray.aspx):

Please Login or Register  to view this content.

Produces this: http://i.imgur.com/OSLVlsS.png which isn't ideal.

A raw implementation of Fisher-Yates yields better results:

Please Login or Register  to view this content.

Produces this: http://i.imgur.com/u2R0IC9.png, which is exactly what I'm after, unfortunately the use of a worksheet function call has a huuuuuuge impact on performance.

This leads to my next question, I was under the impression that the VBA Int function would always round down, so should be a replacement for Floor, however I've got artifacts in my visualization showing that something isn't quite right, this is what I've got:

Please Login or Register  to view this content.

And these artifacts are consistent in their location:
http://i.imgur.com/KCYUeh5.png
http://i.imgur.com/Q0ljZ6I.png

Any takers on how to improve the algorithm? - latest workbook attached

Hy, Kyle,

How about either of these?

Please Login or Register  to view this content.

Test1 always has the numbers 10 to n-1 in each row. Test2 shuffles the numbers 0 to n^2-1.

An in-situ 2D F-Y shuffle would avoid the need for the copy.

EDIT: This seems like it's not worth the time:

Please Login or Register  to view this content.

Consistently at Column 40, Row 35 (in the spreadsheet) when using the the Int method is a field that is always significantly in variance to the norm over large iterations - it swings both ways.

It also occurs in "ShuffleArrayInPlace" in the same location once one reverses the loop order (or the inverse location if one leaves as is)

Similarly Row 47 is consistently regular.

One wouldn't expect this over a large enough sample size if the sorting were properly random - and indeed it's not present on the Application.Floor method.

Interestingly removing Randomize gives a better distribution

Originally Posted by Kyle123

Interestingly removing Randomize gives a better distribution

By your appearance measure, yes. In another thread over the last month, someone made the same argument using the same method - a picture. The application was simulating dice rolls.

Another measure of randomness, though, is predictability, and Rnd has such a short cycle that in about 12 rolls of a single die, you can predict the balance of the rolls. So randomizing in every call is totally appropriate.

Thanks shg.

So how is it applied in this case? I ask because maths is not my strong point. Why does randomizing more frequently (or setting a new seed as I understand it to be) offer less random results? If the cycle is short, one would assume that reseeding regularly is required to maintain a random distribution - a short cycle would generate a pattern.

If one increases frequency of generating a new by placing the randomize call within the inner iteration (rather than before it) the distribution becomes yet less even - this is easily demonstrated through the visualisation.

How was this demonstrated using a picture? Or do you mean a visual representation as I have?

Here's the thread: http://www.mrexcel.com/forum/excel-q...dbetweens.html

Rnd produces a lovely pattern of numbers, it's just so short than you can look at a few numbers (you only need one if you look at the entire Single) and figure out where it is, so you know what's coming next.

I would not put the Randomize in the shuffle function. I think it is meritorius that Rnd can be seeded (or the VBA reset) to generate a fixed sequence of random numbers for testing.

RAND() has a hugely longer cycle (about 27 trillion) than Rnd's 2^24 (~ 17M), but it's about 1000 times slower

Int() rounds toward -infinity, and TRUNC() rounds toward 0, but there is no difference for positive numbers.

Which combination of routines do you find anomalous, Kyle?

I would add that WF.RandBetween was hosed in UDFs in Excel 2003, and there is a mind-bending anomaly described in http://www.excelforum.com/excel-form...functions.html

EDIT: And which of Chip's codes?

In the workbook, "shufflearrayinplace" is not ideal (it's chips), there is a strong bias against a number remaining where it starts as well as a sliding bias on the last element. Here is the output http://i.imgur.com/OSLVlsS.png note the variance at 11,16 this is the same as below allowing for the off by one (the iteration is reversed)

Application.Floor provides an even distribution, however take a look at the linked pictures (or run fischeryates using my code in the workbook) and you'll see that there's a bias on row 57, as well as an element at col 40 row 35 in the spreadsheet that is consistently at variance to the norm (can be positive or negative)

The linked images demonstrate the behaviour, but it's reproduceable by running the code - you can try all three variants in my workbook

In Sub test from post #3, with one iteration, all of the values in matrix are between 0 and 5.

While we're here, a 2D shuffle:

Please Login or Register  to view this content.

Originally Posted by Kyle123

Does that sound feasible?

Timer on my 'puter is 256 ticks/s (about 4 ms between ticks), so that loop would use the same value many times. Help sez,

[when the number argument is omitted] Randomize uses the return value from the Timer function as the new seed value. <...> To repeat sequences of random numbers, call Rnd with a negative argument immediately before using Randomize with a numeric argument. Using Randomize with the same value for number does not repeat the previous sequence.

... and a quick test confirms that, but I don't know what other issues it might cause.

I should have said yesterday that the first thing I did was remove the Randomize statement from your shuffle routine.

Finally, calibrated (for colour) Fisher Yates - no randomization in shuffle:
http://i.imgur.com/1uT6U9d.png

I don't understand how you have the CF set up for that; there isn't the variation across the spectrum of colors that the CF defaults to. Could you post the current workbook and say which routine generates that?