Produce randomised output pairs from non-random input pairs

README.md

Produce Random Pairs Given Non-random Input Pairs

Mechanism

It's tempting to flatten the input into a single list, then use one of rand's built-in methods to keep choosing two elements at random until the list is empty or some variation on this. However, this can't guarantee that none of the output pairs are the same as the input pairs.

Instead, we use a two-step algorithm:

1. Perform a Fisher-Yates shuffle (O(n)) of the list of input pairs, randomising their order
2. Iterate over chunks of the shuffled pairs, two pairs at a time.
   • for each chunk, swap the pair members: (a, b), (c, d) -> (a, d), (c, b) This guarantees that no output pair is equal to an input pair.

This is almost certainly not optimal, but it's good enough.

Cargo.toml

[package]
name = "shufflers"
description = "Produce random output pairs from non-random input pairs"
version = "0.1.0"
edition = "2021"
license = "BlueOak-1.0.0"

[dependencies]
rand = "0.8.5"

main.rs

use std::error;

use rand::seq::SliceRandom;
use rand::thread_rng;

fn swap<'a>(pairs: &'a [[&'a str; 2]]) -> impl Iterator<Item = [&'a str; 2]> {
    pairs
        .chunks(2)
        .flat_map(|chunk| vec![[chunk[0][0], chunk[1][1]], [chunk[1][0], chunk[0][1]]])
}

fn shuffle_and_randomise<'a>(
    pairs: &'a mut Vec<[&'a str; 2]>,
) -> Result<Vec<[String; 2]>, Box<dyn error::Error>> {
    if pairs.len() < 2 {
        return Err("Not enough pairs! Provide at least two".into());
    }
    let mut rng = thread_rng();
    pairs.shuffle(&mut rng);

    let new_pairs = if pairs.len() % 2 == 0 {
        // No need for any shenanigans
        pairs
            .chunks(2)
            .flat_map(swap)
            .map(|pair| [pair[0].to_string(), pair[1].to_string()])
            .collect()
    } else {
        // we can't pair adjacent chunks if we have an odd number of chunks
        // snip last element
        let mut paired: Vec<_> = pairs[..pairs.len() - 1].chunks(2).flat_map(swap).collect();

        // now swap members between snipped last element and new last element
        let new_last = paired.pop().unwrap();
        // swap new last element members with original last element members
        let combined = [new_last, *pairs.last().unwrap()];
        let mut swapped: Vec<_> = swap(&combined).collect();
        // and add the newly recombined chunks back to the shuffled pairs
        paired.append(&mut swapped);
        paired
            .iter()
            .map(|pair| [pair[0].to_string(), pair[1].to_string()])
            .collect()
    };
    Ok(new_pairs)
}

fn main() {
    let mut pairs = vec![["a", "b"], ["c", "d"], ["e", "f"]];
    let randomised = shuffle_and_randomise(&mut pairs);
    match randomised {
        Ok(res) => println!("{:?}", &res),
        Err(e) => println!("Something went wrong: {:?}", e),
    }
}