A Weekly Rust🦀 Pill #2

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:

1. Start with an array containing elements to be shuffled.
2. Initialize an index i to the last element of the array.
3. Repeat the following steps until i reaches 0:
   • Generate a random index j between 0 and i.
   • Swap the element at index i with the element at index j.
   • Decrement i by 1.

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);
}

References

• Fisher-Yates Algorithm
• Rand crate