Buddy-Up: Create Unique Pairs over Time

Apparently trying to pair people up is a more common problem than I imagined. From teachers trying to pair up students over the course of a semester to weekly work huddles, doing this without repeating pairs gets very difficult after a while! Seeing my wife struggle with this for over an hour motivated me to come up with a solution: Introducing Buddy-Up!

The Problem

The problem is that there are lots of ways to create pairs of people from a group, and most of them suck, i.e. repeat pairs. What we want is a way to:

1. Pair people up (duh)
2. Not have pairs repeat
3. Allow the group to change over time to account for new members or absences

This means we have keep a history and we need an algorithm that doesn't need to explore the whole problem space to find a solution. I decided to go with a genetic algorithm. It tries to act like natural selection and works pretty well, and I'll let you find out more about it on your own. Only the fitness function is really important here, and I discuss it below. Let's look at some numbers.

The Math

For $n$ persons there are $n!$ ways to arrange them in a row so we can pair them up two-by-two, like (1 2)(3 4) etc. But we don't care about how the pairs are ordered relative to each other, i.e. (1 2)(3 4) is equivalent (for us) to (3 4)(1 2). There are $(\frac{n}{2})!$ ways to arrange the pairs, so we'll divide by that. We also don't care how the pairs are ordered within, i.e. (1 2) is equivalent (for us) to (2 1). So we only keep half of all the pairs, that is $2^\frac{n}{2}$. Putting it all together, there are $k$ ways to form pairs from $n$ people, such that:

$$k = \frac{n!}{2^\frac{n}{2}(\frac{n}{2})!}$$

That gets big really fast. For $n=10$, $k \approx 1000$; for $n=20$, $k \approx 650,000,000 $.

Then I needed a way to save pairs as history. Fortunately, there are a lot fewer unique pairs. Arranging pairs in a $n x n$ matrix, we can throw out the diagonal (because no one will be paired up with just themselves), and half of the rest, because it's symmetric along the diagonal (because pairs don't have an internal order), so that we end up with $p$ unique pairs:

$$p = \frac{n^2 - n}{2}$$

That's manageable. For $n=10$ that's $p = 45$ pairs, for $n=20$ that's $p = 190$. Easy peasy.

Finally, we note that these pairs start repeating after $n-1$ meetings. That's intuitive, but can also be proved: if $m$ is the number of meetings, we will get repetition after the number of meetings times the number of pairs per meeting is equal to the number of unique pairs, i.e. when all our pairing has exhausted the number of unique pairs: $m \frac{n}{2} = p = \frac{n^2 - n}{2}$ which simplifies to $m=n-1$. This is important to set expectations: at best, you will get repeating pairs after $n-1$ meetings. Ideally only 1 per meeting until everyone has met with everyone else again (another $n-1$ meetings), but I don't know if the algorithm can provide that. Even so, it does a pretty good job!

The Solution

The app reads a CSV file of people and outputs a table of pairs plus the history, described below. A pairing table looks like this:

+---------+-------+
| Bjorn   | Peter |
|---------+-------|
| Alice   | Karl  |
|---------+-------|
| Bob     | Simon |
|---------+-------|
| David   | Frank |
|---------+-------|
| Charlie | John  |
+---------+-------+

The History File

A colleague suggested that I save off the pairings for each session in a separate file and just parse that back in for each new run. It'd take a lot of meetings to make that very slow, so I ran with it. A history file is just a Vec of tuples:

[
  [
    {
      "id": 10,
      "name": "Bjorn"
    },
    {
      "id": 5,
      "name": "Peter"
    }
  ],
  [
    {
      "id": 6,
      "name": "Alice"
    },
    {
      "id": 1,
      "name": "Karl"
    }
  ],
  [
    {
      "id": 7,
      "name": "Bob"
    },
    {
      "id": 3,
      "name": "Simon"
    }
  ],
  [
    {
      "id": 9,
      "name": "David"
    },
    {
      "id": 4,
      "name": "Frank"
    }
  ],
  [
    {
      "id": 8,
      "name": "Charlie"
    },
    {
      "id": 2,
      "name": "John"
    }
  ]
]⏎

The Algorithm and Fitness Function

I am not an expert in genetic algorithms and only learned enough to model this problem in terms of chromosomes and genes with the genetic_algorithm crate. The documentation is good and the examples very helpful to adapt to my own use case. Kudos!

On each run, the app takes all the history files and creates a HashMap with pairs as the key and the number of times they have been paired up as the value. That value gets added up for every pair in a potential pairing to score it. Fewer is better. This sum is the score for that pairing, and the algorithm will try and minimize that score to find the ideal (non-repeating) pairing.

The result is saved in a new history file and displayed as a table.

Future Work

A CLI app is probably not the best user experience for most of the folks who need to pair people up, so I may look into creating a GUI app as well, probably with Tauri. Not sure when I'll get to that, GUIs don't really interest me, but I have been intrigued by Tauri and Leptos, and you can build apps using both.