Every once in a while, we need a random sequence. Whether to test a data structure’s performance or to run probabilistic unit tests, the provided `rand` primitive from your favorite programming language has several limitations. First, it’s been known for a while that if most implementations of the C standard library `rand()` function are not very random, despite being “good enough” in great many cases. Second, and more importantly, it does not allow you to easily control the period nor to generate a permutation on , for example.

There are many methods of generating pseudo-random number sequences. Not all exhibit the same properties and, accordingly, a method may be more useful in one case and perfectly useless in another. High quality pseudo-random number generation is a notoriously hard endeavor, but there is a number of very simple algorithms that will get you out of trouble for certain specific tasks. Let us consider, for example, the example where the pseudo-random generator must generate the numbers in exactly once, in a random order, of course, in exactly draws.

Read the rest of this entry »