Consider a method to randomly shuffle elements in an array. How would you write a simple yet robust unit test to make sure that this is working?

I've come up with two ideas, both of which have noticeable flaws:


Shuffle the array, then make sure its order differs from before. This sounds good, but fails if the shuffle happens to shuffle in the same order. (Improbable, but possible.)
Shuffle the array with a constant seed, and check it against the predetermined output. This relies on the random function always returning the same values given the same seed. However, this is sometimes an invalid assumption.


Consider a second function which simulates dice rolls and returns a random number. How would you test this function? How would you test that the function...


never returns a number outside the given bounds?
returns numbers in a valid distribution? (Uniform for one die, normal for large numbers of dice.)


I'm looking for answers offering insight into testing not only these examples but random elements of code in general. Are unit tests even the right solution here? If not, what sort of tests are?



Just to ease everyone's mind I'm not writing my own random number generator.

I don't think unit tests are the right tool for testing randomness.  A unit test should call a method and test the returned value (or object state) against an expected value.  The problem with testing randomness is that there isn't an expected value for most of the things you'd like to test.  You can test with a given seed, but that only tests repeatability.  It doesn't give you any way to measure how random the distribution is, or if it's even random at all.

Fortunately, there are a lot of statistical tests you can run, such as the Diehard Battery of Tests of Randomness.  See also:


How to unit test a pseudo random number generator?


Steve Jessop recommends that you find a tested implementation of the same RNG algorithm that you're using and compare its output with selected seeds against your own implementation.
Greg Hewgill recommends the ENT suite of statistical tests.
John D. Cook refers readers to his CodeProject article Simple Random Number Generation, which includes an implementation of the Kolmogorov-Smirnov test mentioned in Donald Knuth's volume 2, Seminumerical Algorithms.
Several people recommend testing that the distribution of the numbers generated is uniform, the Chi-squared test, and testing that the mean and standard deviation are within the expected range.  (Note that testing the distribution alone is not enough.  [1,2,3,4,5,6,7,8] is a uniform distribution, but it's certainly not random.)

Unit Testing with functions that return random results


Brian Genisio points out that mocking your RNG is one option for making your tests repeatable, and provides C# sample code.
Again, several more people point to using fixed seed values for repeatability and simple tests for uniform distribution, Chi-squared, etc.

Unit Testing Randomness is a wiki article that talks about many of the challenges already touched on when trying to test that which is, by its nature, not repeatable.  One interesting bit that I gleaned from it was the following:


  I've seen winzip used as a tool to measure the randomness of a file of values before (obviously, the smaller it can compress the file the less random it is).


