Ok, in this codepen I already found a Round Robin tournament scheduling algorithm: https://codepen.io/Piconey/pen/mwPamw
var players = [
{
playerName: 'Person 1',
},
{
playerName: 'Person 2',
},
{
playerName: 'Person 3',
},
{
playerName: 'Person 4',
},
{
playerName: 'Person 5',
},
{
playerName: 'Person 6',
},
{
playerName: 'Person 7',
},
{
playerName: 'Person 8',
},
{
playerName: 'Person 9',
},
{
playerName: 'Person 10',
},
{
playerName: 'Person 11',
},
{
playerName: 'Person 12',
},
{
playerName: 'Person 13',
},
{
playerName: 'Person 14',
},
{
playerName: 'Person 15',
},
{
playerName: 'Person 16',
},
];
var numberOfRounds = players.length - 1;
function generateRounds() {
for(i = 0; i < numberOfRounds; i++) {
document.write('<h1 class="round">'+'Round ' + (i+1) + '</h1>');
for (var j = 0; j < players.length / 2; j++) {
document.write('<div class="match">' + players[j].playerName + " - " + players[players.length - 1 - j].playerName +'</div>');
}
players.splice(1, 0, players[15]);
players.pop();
}
}
generateRounds();
I use it for a speeddating even where you can date with everyone.
My problem: After every round new people can join the event or leave the event (if they get bored 😉
Note: The latecomers don’t need to date everyone, because they already missed x rounds Note 2: If a lot of people leave, it would be nice to limit the number of rounds so that people don’t need to wait that long between dates
Advertisement
Answer
For a bipartite matching problem like speed dating between separated sets of men and women, you can use a maximum flow algorithm.
Build graph in 4 layers:
- Source node S
- One node for each man
- One node for each woman
- Sink node T
- Fully connect layer 1 to 2 with edge capacity 1
- Fully connect layer 2 to 3 with edge capacity 1
- Fully connect layer 3 to 4 with edge capacity 1
When a person is added, add them as a new node in layer 2 or 3, and fully connect to adjacent layers as above.
When a person is removed, remove their nodes in layer 2 and 3 and all edges from their node.
At each round, use max flow algorithm to identify your pairings. After round, set capacity of layer 2->layer 3 edges involved in the pairings to 0. This will prevent the same two people from being matched again in subsequent rounds.
Heuristic: You can modify the max flow algorithm to pair up the people with the either the fewest dates or the most rounds sat out first, so if an odd number of people exist, neither the newest person nor the same person is sitting out rounds.
Extensions: You can implement preferences to restrict the set of potential matches by filtering the set of edges added between layers 2 and 3.
Time: Roughly O(n^3) per round
Some javascript max flow package on github, never tried it so good luck: https://github.com/orcaman/flownetwork
For an anyone to anyone matching problem, you must replace the max flow algorithm with the more complex Blossom algorithm.
Like max flow, this algorithm iteratively refines matches by finding augmenting paths then modifying its current set of matches.
The input for this algorithm is:
- Add a node for each person
- Fully connect all nodes
As in the bipartite case, at the end of each round, remove all edges corresponding to matches in previous rounds, preventing the same two people from being matched.
When a new person joins, add a node and fully connect them to other people.
When a person leaves, remove their node and all connected edges.
The Blossom algorithm is better described here https://en.wikipedia.org/wiki/Blossom_algorithm
A quick search shows several javascript implementations of this algorithm, your mileage may vary.