Generating random rounds of unique pairs-CodePudding

I have an even number of participants. I want to generate n seemingly random rounds of pairings of participants, such that every participant gets paired up with another one and that no pair ever occurs more than once.

For example:

Suppose I have the participants a, b, c, d, e and f.

A first possible first round of pairings would look like this:

(a, b), (c, d), (e, f)

A second round would for example then look like this:

(a, c), (b, e), (d, f)

A bad example for a second round would be:

(a, c), (b, d), (e, f)

Which has the repeated pairing (e, f) and would therefore not be considered valid.

Pseudo code suffices. Thanks.

EDIT: I forgot to add that I want the pairings to seem random. NOT like a round-robin.

CodePudding user response：

Suppose you know how to apply a certain round-robin algorithm, but you wish to make the pairs "more random".

Attend to the "assign" verb:

All competitors are assigned to numbers, and then paired ...

You are free to assign ordinal position numbers arbitrarily. You might have a list in some python implementation:

competitors = ['Alice, 'Bob', ... ]

But the alphabetic order is undesirable. So shuffle them:

import random

random.shuffle(competitors)

Now feed that new permutation to your favorite round-robin algorithm.

In general, when given the results of any round-robin algorithm that proposes a sequence of pairings, you are free to permute that result to produce a related random sequence which also pairs each competitor against each of the others.

CodePudding user response：

Using this great answer I was able to implement the solution in Rust:

use itertools::Itertools;
use rand::seq::SliceRandom;

fn main() {
    let participants = vec!["A", "B", "C", "D", "E", "F"];

    let all_rounds = all_rounds(4, participants);
    println!(
        "{}",
        all_rounds
            .into_iter()
            .map(|round| round
                .into_iter()
                .map(|pair| format!("{:?}", pair))
                .join(", "))
            .join("\n")
    );
}

fn all_rounds(num_rounds: u32, mut participants: Vec<&str>) -> Vec<Vec<(&str, &str)>> {
    participants.shuffle(&mut rand::thread_rng());
    (0..num_rounds)
        .map(|_| {
            let round = participants
                .iter()
                .copied()
                .zip(participants.iter().copied().rev())
                .take(participants.len() / 2)
                .collect();
            let last = participants.pop().unwrap();
            participants.insert(1, last);
            round
        })
        .collect()
}

Thank you all very much.