Problem
A random pair generator takes a list of items (students, names, tasks, players) and produces pairs that are intended to be unbiased and unpredictable. The goal is to describe a method that makes each possible pairing equally likely (when the list size is even), explain how an odd-sized list is handled, and count how many different pairings exist.
Step-by-step method used by a random pair generator
A standard approach is: (1) randomize the order of the list uniformly, then (2) group consecutive items into pairs. This works because “uniform shuffle” means every permutation of the list has the same probability.
- Label the items as distinct entries (even if two entries have the same text, treat them as different positions in the input list).
- Shuffle uniformly: generate a random permutation where each of the \(n!\) possible orders occurs with probability \(1/n!\). A classic way to achieve this is the Fisher–Yates shuffle driven by a good random source.
- Pair consecutively: after shuffling, create pairs \((1,2), (3,4), (5,6), \dots\).
- If \(n\) is odd, one item remains unpaired (often shown as a “leftover” or “bye”), while the other \(n-1\) items form \((n-1)/2\) pairs.
Fairness criterion (even \(n\))
When the shuffle is uniform, the “pair consecutive items” rule produces a uniform random matching: each distinct set of pairs has the same probability. The combinatorics below shows why.
How many distinct pairings exist when \(n\) is even?
Assume \(n\) is even. A “pairing” means partitioning the \(n\) distinct items into \(n/2\) unordered pairs (order within a pair does not matter, and the set of pairs has no order). The number of such pairings is the double factorial:
\[ (n-1)!! = (n-1)(n-3)(n-5)\cdots 3\cdot 1. \]
A derivation based on counting choices:
- Choose a partner for item 1: \(n-1\) options.
- Remove that pair; among the remaining \(n-2\) items, choose a partner for the next unpaired item: \(n-3\) options.
- Continue until all items are paired.
Multiplying the odd integers yields \((n-1)!!\). Equivalently, \[ (n-1)!! = \frac{n!}{2^{n/2}\,(n/2)!}. \]
Why shuffling then pairing gives equal probability for each pairing
Each fixed pairing corresponds to many shuffled orders: within each pair the two items can swap (\(2^{n/2}\) possibilities), and the \(n/2\) pairs can appear in any order (\((n/2)!\) possibilities). Therefore, each pairing is represented by exactly \(2^{n/2}(n/2)!\) permutations.
Since the shuffle is uniform over \(n!\) permutations, the probability of any particular pairing is \[ \frac{2^{n/2}(n/2)!}{n!} \;=\; \frac{1}{(n-1)!!}, \] which is the same for all pairings.
Worked example
Suppose there are \(n=9\) names. After a uniform shuffle, the first 8 names form 4 pairs and 1 name remains unpaired. A sample shuffled order is shown below.
| Position after shuffle | Item | Pairing result |
|---|---|---|
| 1 | Ana | Pair 1: (Ana, Ben) |
| 2 | Ben | |
| 3 | Cara | Pair 2: (Cara, Dritan) |
| 4 | Dritan | |
| 5 | Elira | Pair 3: (Elira, Fadil) |
| 6 | Fadil | |
| 7 | Genti | Pair 4: (Genti, Hana) |
| 8 | Hana | |
| 9 | Ilir | Unpaired (leftover/bye) |
For an even-size list such as \(n=8\), the number of distinct outcomes is \[ (8-1)!! = 7\cdot 5\cdot 3\cdot 1 = 105. \] A random pair generator that shuffles uniformly and pairs consecutively selects one of these 105 pairings with probability \(1/105\).
Visualization of a pairing
Common practical details
- Odd \(n\): decide whether the last item is left unpaired, or whether a “triple” is allowed (triples are not pairs, so the result is no longer a pure pairing).
- Constraints: avoiding specific pairings (e.g., “do not pair two people from the same group”) requires constraint-handling logic; simple shuffling may need retries or a structured matching algorithm.
- Reproducibility: storing a seed value allows the same random pair generator output to be reproduced later (useful in experiments and classroom activities).
Summary
A random pair generator can be implemented by a uniform shuffle followed by consecutive pairing. For even \(n\), there are \((n-1)!!\) distinct pairings, and each occurs with probability \(1/(n-1)!!\) under a truly uniform shuffle.