Implement Fisher-Yates shuffle in Ruby

Some time ago, for a little personal project, I needed to implement a shuffle algorithm. After some research I decided to use the Fisher-Yates algorithm.

Simply stated, this algorithm works like this:

  1. Given an array a = [1, 2, 3, 4, 5, 6, 7, 8]
  2. Get a random number i between 0 and n - 1 where n = a.length
  3. At this point swap array[i] with array[n]
  4. Restart.
  5. But, the next time the random i must be calculated between 0 and n - 2 and so on until you get to n = 0

In this way an element from the back of the array is swapped with an element from the front and waits to be shuffled.

Here is a solution to implement it in ruby:

class Array
  def shuffle!
    n = length
    while n > 0
      i = rand(n -= 1)
      self[i], self[n] = self[n], self[i]
    end
    self
  end
end

puts (1..8).to_a.shuffle!.join(‘,’)
puts (1..52).to_a.shuffle!.join(‘,’)

For the next step I want to implement a weighted-shuffle algorithm, but at the moment I’m still missing something. I hope to be ready for the next post!

Bye and see you soon!

Leave a Reply

wpDiscuz