1

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.

weisbrja
  • 164
  • 10
  • What have you tried? Where are you facing an issue? – Abhinav Mathur Jan 15 '23 at 17:25
  • 1
    It is a well known problem of generating round roubin turnaments (e.g. chess turnaments); just consult some algorithms in the internet, e.g. https://en.wikipedia.org/wiki/Round-robin_tournament – Dmitry Bychenko Jan 15 '23 at 17:49
  • Related questions: [Get n * k unique sets of 2 from list of length n in Python](https://stackoverflow.com/questions/64604793/get-n-k-unique-sets-of-2-from-list-of-length-n-in-python/64606498#64606498) and [How do I write an efficient Pair Matching algorithm?](https://stackoverflow.com/questions/70583166/how-do-i-write-an-efficient-pair-matching-algorithm/70586287#70586287) – Stef Jan 15 '23 at 19:02
  • I read about the Round-robin algorithm, but I couldn't figure out how to make the pairs "more" random. – weisbrja Jan 15 '23 at 19:34

2 Answers2

2

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.

J_H
  • 17,926
  • 4
  • 24
  • 44
  • You can also permute the rounds and (if the order is meaningful) the matches within each round. – David Eisenstat Jan 16 '23 at 00:10
  • But can am I not only allowed to permutate the order of the competitors in the beginning, and not between rounds? Would that not mess up the algorithm? – weisbrja Jan 16 '23 at 20:56
1

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.

weisbrja
  • 164
  • 10