A round robin tournament has n players. In each round, all players face each other once. Number of games per round is n * (n-1) / 2. Number of rounds is unlimited. Games are played one at a time without breaks, so the only way to get rest is to not play consecutive games.
How to find the best order of games with the following goals (in priority order)?
I didn't figure out any other way to achieve this than the brute-force way: check each possible permutation and keep the best one in memory.
I had 7 people in my scenario. For n = 7, the count of games is 7 * 6 / 2 = 21, meaning that the count of permutations is 21! = 51090942171709440000. Of course, it's practically impossible to check that many permutations, so I ended up just implementing a program which creates random lists up to m. It was enough for my purposes at the time. The best permutation I found with this method (out of 100 million) had 9 one day rests and they were divided pretty equally among different players.
What is the most efficient way to get the best permutation?
For possible code examples I would prefer Java, JavaScript, or Swift.
Rather than try random permutations, we can apply a biased random key genetic algorithm (BRKGA). This generic optimization technique can find a solution for n=7 with only four one-match rests, all by different players:
1 4 1
1 3
0 4
2 5
1 6
2 3
4 5
0 6
3 5
1 2
4 6
0 3
1 5
2 6
3 4
0 1
2 4
3 6
0 5
1 4
0 2
5 6
C++ code:
#include <algorithm>
#include <array>
#include <iostream>
#include <limits>
#include <numeric>
#include <random>
#include <tuple>
#include <utility>
#include <vector>
namespace {
constexpr int kNumPlayers = 7;
constexpr int kNumMatches = kNumPlayers * (kNumPlayers - 1) / 2;
class Solution {
public:
template <typename Generator> static Solution Random(Generator &generator);
template <typename Generator>
Solution MateWith(const Solution &that, Generator &generator) const;
std::array<std::tuple<int, int>, kNumMatches> Matches() const;
private:
Solution() = default;
std::array<double, kNumMatches> keys_;
};
template <typename Generator> Solution Solution::Random(Generator &generator) {
Solution solution;
std::uniform_real_distribution<double> uniform;
for (int k = 0; k < kNumMatches; k++) {
solution.keys_[k] = uniform(generator);
}
return solution;
}
template <typename Generator>
Solution Solution::MateWith(const Solution &that, Generator &generator) const {
Solution child;
std::bernoulli_distribution biased_coin(0.7);
for (int k = 0; k < kNumMatches; k++) {
child.keys_[k] = biased_coin(generator) ? this->keys_[k] : that.keys_[k];
}
return child;
}
std::array<std::tuple<int, int>, kNumMatches> Solution::Matches() const {
std::array<std::tuple<double, std::tuple<int, int>>, kNumMatches> rankings;
{
int k = 0;
for (int i = 0; i < kNumPlayers; i++) {
for (int j = i + 1; j < kNumPlayers; j++) {
rankings[k] = {keys_[k], {i, j}};
k++;
}
}
}
std::sort(rankings.begin(), rankings.end());
std::array<std::tuple<int, int>, kNumMatches> matches;
for (int k = 0; k < kNumMatches; k++) {
matches[k] = std::get<1>(rankings[k]);
}
return matches;
}
std::vector<std::tuple<int, int>>
Rests(const std::array<std::tuple<int, int>, kNumMatches> &matches) {
std::array<int, kNumMatches> last_match;
for (int k = 0; k < kNumMatches; k++) {
last_match[std::get<0>(matches[k])] = k - kNumMatches;
last_match[std::get<1>(matches[k])] = k - kNumMatches;
}
std::vector<std::tuple<int, int>> rests;
for (int k = 0; k < kNumMatches; k++) {
auto plays = [&](int i) {
rests.push_back({k - 1 - last_match[i], i});
last_match[i] = k;
};
plays(std::get<0>(matches[k]));
plays(std::get<1>(matches[k]));
}
return rests;
}
std::tuple<int, int, int>
Objective(const std::array<std::tuple<int, int>, kNumMatches> &matches) {
auto rests = Rests(matches);
int min_rest = std::get<0>(*std::min_element(rests.begin(), rests.end()));
std::array<int, kNumPlayers> player_to_min_rest_count;
std::fill(player_to_min_rest_count.begin(), player_to_min_rest_count.end(),
0);
for (auto [rest, player] : rests) {
if (rest == min_rest) {
player_to_min_rest_count[player]++;
}
}
return {-min_rest,
std::accumulate(player_to_min_rest_count.begin(),
player_to_min_rest_count.end(), 0),
*std::max_element(player_to_min_rest_count.begin(),
player_to_min_rest_count.end())};
}
std::vector<Solution> SortByFitness(const std::vector<Solution> &population) {
std::vector<std::tuple<std::tuple<int, int, int>, const Solution *>> tagged;
tagged.reserve(population.size());
for (const Solution &solution : population) {
tagged.push_back({Objective(solution.Matches()), &solution});
}
std::sort(tagged.begin(), tagged.end());
std::vector<Solution> sorted_population;
sorted_population.reserve(population.size());
for (auto [objective, solution] : tagged) {
sorted_population.push_back(*solution);
}
return sorted_population;
}
template <typename Generator> Solution BRKGA(Generator &generator) {
static constexpr int kRounds = 20000;
static constexpr int kNumEliteSolutions = 300;
static constexpr int kNumMatedSolutions = 600;
static constexpr int kNumRandomSolutions = 100;
static constexpr int kNumSolutions =
kNumEliteSolutions + kNumMatedSolutions + kNumRandomSolutions;
std::vector<Solution> population;
population.reserve(kNumSolutions);
for (int i = 0; i < kNumSolutions; i++) {
population.push_back(Solution::Random(generator));
}
for (int r = 0; r < kRounds; r++) {
population = SortByFitness(population);
std::vector<Solution> new_population;
new_population.reserve(kNumSolutions);
for (int i = 0; i < kNumEliteSolutions; i++) {
new_population.push_back(population[i]);
}
std::uniform_int_distribution<int> elite(0, kNumEliteSolutions - 1);
std::uniform_int_distribution<int> non_elite(kNumEliteSolutions,
kNumSolutions - 1);
for (int i = 0; i < kNumMatedSolutions; i++) {
int j = elite(generator);
int k = non_elite(generator);
new_population.push_back(
population[j].MateWith(population[k], generator));
}
for (int i = 0; i < kNumRandomSolutions; i++) {
new_population.push_back(Solution::Random(generator));
}
population = std::move(new_population);
}
return SortByFitness(population)[0];
}
void PrintSolution(const Solution &solution) {
auto matches = solution.Matches();
auto objective = Objective(matches);
std::cout << -std::get<0>(objective) << ' ' << std::get<1>(objective) << ' '
<< std::get<2>(objective) << '\n';
for (auto [i, j] : solution.Matches()) {
std::cout << i << ' ' << j << '\n';
}
}
} // namespace
int main() {
std::default_random_engine generator;
PrintSolution(BRKGA(generator));
}