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:
- Given an array
a = [1, 2, 3, 4, 5, 6, 7, 8]
- Get a random number
i
between0
andn - 1
wheren = a.length
- At this point swap
array[i]
witharray[n]
- Restart.
- But, the next time the random
i
must be calculated between0
andn - 2
and so on until you get ton = 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