#pair #up #buddy #people #unique #group #buddy-up

buddy-up-lib

The brains behind the buddy-up crate

2 unstable releases

Uses new Rust 2024

new 0.2.0 Mar 16, 2025
0.1.2 Mar 2, 2025

#4 in #buddy

Download history 149/week @ 2025-02-26 19/week @ 2025-03-05

168 downloads per month

MIT/Apache

13KB
324 lines

Buddy-Up 🎉🥳 Continuous Integration Continuous Deployment Release

Buddy up a changing group of people into unique pairs over time.

Installation

  • Head to the Releases and download the binary for your platform.
  • Install with Cargo: cargo install --locked buddy-up

How to Use

buddy --help has good info.

You could run it like this:

buddy pair --input people.csv --output-dir meeting

Depending on the input, you'll get a table showing the pairings, something like this.

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

The history of pairs is saved in the output-dir

❯ ls meeting/
20250213_205644.json

Feel free to manually edit the history files, they are just JSON.

Input

CSV file of the format:

1,Karl
2,John
3,Simon
4,Frank
5,Peter
6,Alice
7,Bob
8,Charlie
9,David
10,Bjorn

IDs need to be unique and positive, and there need to be an even number of people (because pairs, right?).

Output

In addition to the actual table of pairs shown above, the pairs are saved as history into the given output directory, as JSON.

How it Works

The Problem

Pairing up people is hard. There are algorithms and tools out there to do it, but I hadn't found one that takes into account a changing group and (implied) doesn't require all the pairings to be calculated up front.

The Solution

Buddy-Up generates pairs from the given input, then saves the pairings in the history. The next time Buddy-Up is run, it reads the history and takes it into account in calculating new pairings, which should be unique, at least until everyone has been paired up once already.

Because the problem space is potentially huge, Buddy-Up uses a genetic algorithm to come up with the best pairings. I think it works pretty well, but isn't perfect. Feel free to open an issue if you have ideas for improving it.

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!}{(\frac{n}{2})! * 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 (proving this is left as an exercise for the reader, but it makes sense intuitively, too). 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!

A word on the fitness function

The history saves how many times each pair has met. Fewer is better. The algorithm looks up the score for every pair in each potential pairing and adds them up. This sum is the score for that pairing, and the algorithm will try and minimize that score to find the ideal pairing.

Dependencies

~16MB
~250K SLoC