Speed-dating algorithm update
Jan. 21st, 2016 06:12 pmAh! After some more introspecting on the right terms to google for, I found: https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm
That describes a simple algorithm which works for pairing any number of people into 2s, making sure each meets each other. I hoped there must be one but hadn't realised how simple it was. AFAICT that's minimal (inserting an extra empty place if you start with an odd number, which is unavoidable), making 2x or 2x-1 people meet in 2x-1 rounds, with x pairs per round.
There are a lot of more complicated systems which aim to do things like make an even balance of "home" and "away" games which don't apply here.
However, that doesn't yet obviously generalise to meeting in groups of three (with the aim of meeting each person once, not each possible combination of three). I wonder if there's something to be learned from bridge rotations, which aim to pair each team with each other team, and also with a unique board?
That describes a simple algorithm which works for pairing any number of people into 2s, making sure each meets each other. I hoped there must be one but hadn't realised how simple it was. AFAICT that's minimal (inserting an extra empty place if you start with an odd number, which is unavoidable), making 2x or 2x-1 people meet in 2x-1 rounds, with x pairs per round.
There are a lot of more complicated systems which aim to do things like make an even balance of "home" and "away" games which don't apply here.
However, that doesn't yet obviously generalise to meeting in groups of three (with the aim of meeting each person once, not each possible combination of three). I wonder if there's something to be learned from bridge rotations, which aim to pair each team with each other team, and also with a unique board?