A Weekly Rust🦀 Pill is a post series where on a weekly base, I share some implementations of the most popular algorithms and data structures to share my learnings on Rust 🦀.
Fisher-Yates Shuffle
With the term shuffling, we referee the procedure to randomise a deck of playing cards. It is a crucial task in online gambling, so using an unbiased algorithm to produce a random permutation of the virtual cards’ deck is essential.
One of the most elegant and efficient methods for achieving true randomness is the Fisher-Yates Algorithm, also known as the Knuth Shuffle.
The Fisher-Yates Algorithm, devised by Ronald A. Fisher and Frank Yates in 1938, is a remarkably simple and efficient method to randomly shuffle elements in an array. Unlike naive shuffling approaches that use a random number generator and multiple iterations, the Fisher-Yates Algorithm achieves a uniform and unbiased distribution with a single pass through the array.
The algorithm can be summarised in the following steps:
- Start with an array containing elements to be shuffled.
- Initialize an index
i
to the last element of the array. - Repeat the following steps until
i
reaches0
:- Generate a random index
j
between0
andi
. - Swap the element at index
i
with the element at indexj
. - Decrement
i
by 1.
- Generate a random index
Implementation
To use random number generation in our code, we must add the rand crate to our project, using cargo add
:
cargo add rand
Here below the code:
use rand::distributions::{Distribution, Uniform};
/// Implementation of Durstenfeld variant of Fisher-Yates shuffling algorithm
/// Computational complexity: O(n)
/// See: https://en.m.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
fn fisher_yates<T>(array: &mut Vec<T>) {
let mut rng = rand::thread_rng();
for i in (1..array.len()).rev() {
let dist = Uniform::from(0..i);
let j = dist.sample(&mut rng);
array.swap(j, i);
}
}
We pass to our function fn fisher_yates<T>(array: &mut Vec<T>)
a mutable reference to a list of generic items in this way, we perform an in place shuffle of original vector.
At line let mut rng = rand::thread_rng();
we initialise our random number generator then in the loop starting from the last item i
we sample a value j
from a uniform distribution from 0
to i
, and we swap the element at position i and j.
To test the function, we can run the following main code:
fn main() {
let mut items: Vec<i32> = vec![0, 1, 2, 3, 4, 5, 6, 7, 8];
println!("Before shuffling: {:?}", items);
fisher_yates(&mut items);
println!("After shuffling: {:?}", items);
}
Top comments (0)