by Josh Branchaud on June 29, 2017

How should we break up teams for this game? In what order should we do presentations? Which lunch spot should we go to this week? The need for some randomization arises often. With irb at our fingertips, we often reach for Ruby's shuffle.

But have you ever wondered how shuffle works?

I can imagine writing a loop that randomly shuffles around the contents of an array, but what would I need to do in order to sufficiently and efficiently shuffle an array? What I need is an algorithm.

When I do a google search for "algorithm to shuffle a list", the first result is a Wikipedia article on the Fisher-Yates shuffle.

The Fisher–Yates shuffle is an algorithm for generating a random permutation of a finite sequence—in plain terms, the algorithm shuffles the sequence. The algorithm effectively puts all the elements into a hat; it continually determines the next element by randomly drawing an element from the hat until no elements remain. The algorithm produces an unbiased permutation: every permutation is equally likely.

That description tells me that this algorithm will be both sufficient and efficient. Great, let's proceed.

Here is the pseudocode for the Fisher-Yates shuffle:

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

We can implement that in Ruby no problem. Something like this should work.

class Array
  def fisher_yates_shuffle
    upper = self.length - 1

    upper.downto(1).each do |current_index|
      random_index = rand(current_index + 1)

      temp = self[random_index]
      self[random_index] = self[current_index]
      self[current_index] = temp
    end

    self
  end
end

The idea behind the algorithm is to go from the end to the beginning replacing the value at each position in the array with a value from a random position in the remaining unset portion of the array. This approach will finish in linear time and we can expect to have a well-shuffled array.

But does this approach have anything to do with the way Ruby's shuffle works?

We can do some source-diving to find out. The challenge here as we'll quickly find out is that Ruby's Array class is entirely implemented in C. After cloning Ruby's git repository, we can open up array.c. Searching for shuffle, we find a function called rb_ary_shuffle which makes a call to rb_ary_shuffle_bang. Navigating to rb_ary_shuffle_bang, we find the meat of the implementation (I've omitted some less interesting bits):

rb_ary_shuffle_bang(int argc, VALUE *argv, VALUE ary)
{
    ...

    i = len = RARRAY_LEN(ary);
    RARRAY_PTR_USE(ary, ptr, {
    while (i) {
        long j = RAND_UPTO(i);
        VALUE tmp;
        if (len != RARRAY_LEN(ary) || ptr != RARRAY_CONST_PTR(ary)) {
        rb_raise(rb_eRuntimeError, "modified during shuffle");
        }
        tmp = ptr[--i];
        ptr[i] = ptr[j];
        ptr[j] = tmp;
    }
    }); /* WB: no new reference */
    return ary;
}

If we stare at it for a moment and let the C sink in a bit, we may start to notice the familiarity of this function. We have an i value that starts as the length of the array and is decremented each loop. We produce a random index value from i. We do some array value swapping each step of the way with tmp. Lastly, we return the shuffled array (ary).

As it turns out, Ruby's shuffle implementation also uses the Fisher-Yates Shuffle. Cool!

We've looked at pseudocode, Ruby, and C. We've also learned a bit about algorithms and added the Fisher-Yates Shuffle to our algorithm-toolbelt. Next time you go to shuffle an array, you'll know exactly what is going on behind the scenes.

So, where should we go for lunch?

restaurants = ['Umami Burger',
               'Chicken and Farm',
               'De Cero Tacos',
               'Bad Hunter']
restaurants.fisher_yates_shuffle.first
#=> 'Chicken and Farm'

Cover photo by Anders Jildén on Unsplash