Nine Mohs

I was recently going through a set of commonly asked interview questions and I came across a problem requiring to shuffle a deck of 52 cards in random order. Initially, I found The Knuth or The Fisher Yates shuffle the easiest algorithm to implement.

The Knuth Shuffle makes use of a certain set  of random numbers for creating randomness. Implementing it as Code, obviously required me to make use of the rand() function.

Here’s the actual description of the algorithm from The Art of Computer Programming, Volume 2: Seminumerical Algorithms, page:145. Third Edition. D.E. Knuth

Let X1, X2, …, Xt be a set of t numbers to be shuffed.

P1. [Initialize.] Set j ← t.
P2. [Generate U.] Generate a random number U, uniformly distributed between zero and one.
P3. [Exchange.] Set k ← [jU] + 1. (Now k is a random integer, between 1 and j. Exchange Xk and Xj.
P4. [Decrease j.] Decrease j by 1. If j > 1, return to step P2.

I used my favourite language Ruby to write the code and came up with this :

array = (1..52).to_a
 
lenth = array.length
 
index = (lenth-1)
 
while(index >= 0) do
 
  random_number = rand(index+1)
 
  array[random_number], array[index] = array[index], array[random_number]
 
  index = index - 1
 
end
 
puts array

One of the problem I found was the use of the rand() function.
The use of a randomize function in real life situation is not ideal, say, in a game of Poker(online). One can easily sync the time of our clock to that of the server, If the randomize function is seeded with the number of milliseconds from the system clock as was in the case of the ASF Software’s Poker product.

A Modulus operator is used for restricting the numbers in a particular range. Like in the GNU C Library’s (GlibC) strfry() which can be used for randomizing strings. 

From Wikipedia :

Doing a Fisher-Yates shuffle involves picking uniformly distributed random integers from various ranges. Most random number generators, however—whether true or pseudorandom—will only directly provide numbers in some fixed range, such as, say, from 0 to 232−1. A simple and commonly used way to force such numbers into a desired smaller range is to apply the modulo operator; that is, to divide them by the size of the range and take the remainder. However, the need, in a Fisher-Yates shuffle, to generate random numbers in every range from 0–1 to 0–N pretty much guarantees that some of these ranges will not evenly divide the natural range of the random number generator. Thus, the remainders will not always be evenly distributed and, worse yet, the bias will be systematically in favor of small remainders.

Googling around turned out that sorting it by using UUID’s as a source of random numbers was more easier to implement.
Ruby offers a library for generating UUID’s which uses /dev/urandom on *nix types systems to generate random numbers.
A GUID can be created by these two lines.

require 'guid' 
 
g2 = Guid.new  #a unique GUID every time

It’s typically not faster, as sorting would be O(n log n) compared to the O(n) (linear time) for the Knuth Shuffle.

Wolfram MathWorld has a few mathematical shuffling algorithms and randomization techniques for further mathematical reference.