如何对每个玩家最多休息的循环赛进行排序？

Question

循环赛有 n 名玩家。在每一轮中，所有玩家都会面对面一次。每轮比赛的数量是n * (n-1) / 2。回合数不限。一场比赛没有休息，所以休息的唯一方法就是不要连续比赛。

如何找到具有以下目标的最佳游戏顺序（按优先顺序）？

最大化休息的最小长度，即同一个人再次比赛之前的比赛次数
将每轮最小休息的计数最小化
尽可能平均分配最小的休息时间给球员

除了蛮力方法之外，我没有想出任何其他方法来实现这一点：检查每个可能的排列并在内存中保留最好的一个。

我的场景中有 7 个人。对于n = 7，游戏的数量是7 * 6 / 2 = 21，也就是说排列的数量是21! = 51090942171709440000。当然，检查这么多排列实际上是不可能的，所以我最终只是实现了一个程序，它创建最多 m 个随机列表。这对我当时的目的来说已经足够了。我用这种方法找到的最佳排列（在 1 亿个中）有 9 个一天的休息时间，并且在不同玩家之间平均分配。

获得最佳排列的最有效方法是什么？

对于可能的代码示例，我更喜欢 Java、JavaScript 或 Swift.

Answer 1

生成所有对的算法相当简单：

将球员排成两排。在每一轮中，顶级玩家都会遇到来自下排的相应玩家。如果玩家人数为奇数，则剩下的玩家。

A B C
D E F
A:D B:E C:F

回合结束后，除第一个玩家以外的所有玩家循环移动

A D B
E F C
A:E D:F B:C 

A E D
F C B
A:F E:C D:B
...

请注意，如果我们使用上面的游戏顺序（从左到右配对），则同一玩家不会参加后续的两场游戏（少数情况除外）

似乎 2*N 玩家的最小休息时间是 N-1（最长的是 N+1）：

A B C D E F
G H I J K L
AG BH CI DJ EK FL 

A G B C D E 
H I J K L F 
AH GI BJ CK DL EF

Answer 2

我们可以应用有偏随机密钥遗传算法 (BRKGA)，而不是尝试随机排列。这种通用优化技术可以找到 n=7 的解决方案，只有四场单场比赛休息，全部由不同的球员进行：

C++代码：

#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));
}

如何对每个玩家最多休息的循环赛进行排序？

How to sort round robin tournament with maximum rests per player?

algorithm

sorting

round-robin