### Ruby

# Do The Shuffle

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.

## 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]
```

## An Implementation

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?

## A Real-World Implementation

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!

## A Conclusion

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