分发球员表 [英] Distributing players to tables

问题描述

考虑 N = 4K 的球员， K 表和一些部族，使得每个成员都可以属于一个氏族。一个氏族最多只能包含 K 播放器。

Consider N = 4k players, k tables and a number of clans such that each member can belong to one clan. A clan can contain at most k players.

我们要组织一个比赛3回合，这样，对于每个座位正好4名球员表，2号球员坐在那里是同一家族的一部分，并为后来的几轮，2号球员坐在那里已经坐同桌了。所有玩家玩几轮。

We want to organize 3 rounds of a game such that, for each table that seats exactly 4 players, no 2 players sitting there are part of the same clan, and, for the later rounds, no 2 players sitting there have sat at the same table before. All players play all rounds.

我们如何才能做到这一点有效，如果 N 可以约〜80 大？

How can we do this efficiently if N can be about ~80 large?

我想到了这一点：

for each table T:
  repeat until 4 players have been seated at T:
    pick a random player X that is not currently seated anywhere
    if X has not sat at the same table as anyone currently at T AND
       X is not from the same clan as anyone currently at T
       seat X at T
       break

我不知道这是否会永远结束，或者如果它能够卡住，即使有一个有效的分配。即使这个工作，有没有更好的办法做到这一点？

I am not sure if this will always finish or if it can get stuck even if there is a valid assignment. Even if this works, is there a better way to do it?

推荐答案

如果总有那么究竟每个战队ķ球员（即4氏族），你就知道应该永远是1人一个氏族的一张桌子。在这种情况下，我认为这是有可能拿出一些predefined轮换方案，其中每个球员，这取决于氏族他来自，移动表固定数量的进一步提高。

If there are always exactly k players per clan (i.e. 4 clans), you know there should always be 1 person of a clan at a table. In that case, I think it's possible to come up with some predefined rotation scheme where each player, depending on the clan he's from, moves a fixed number of tables further.

我不认为这是可能的，如果氏族的数量可以超过4（或我没有看到它，反正）

I don't think that's possible if the number of clans can be more than 4 (or I don't see it, anyway)

我觉得你的算法是pretty的好。可以prevent它从从不终止（如果没有有效的解决方案），同时仍然保持了随机化行为的一种方法是不选择一个随机播放无限的，但洗牌的离座球员名单一次，并处理每个玩家从这个名单依次为：

I think your algorithm is pretty good. One way you can prevent it from never terminating (if there are no valid solutions) while still maintaining the randomized behaviour is to not pick a random player infinitely, but to shuffle the list of unseated players once, and process each player from this list in turn:

修改：我忘了遍历回合，包括这个算法以及

Edit: I forgot to iterate through the rounds, included this in the algorithm as well.

for each round R in {1, 2, 3}
  for each table T:
    UP = a randomly shuffled list of unseated players
    for each player X from UP
      if there are less than 4 people seated at T AND
         X has not previously sat with any of the players currently at T AND
         X is not from the same clan as anyone currently at T
           seat X at T

    //No more players left to try for this table
    if T has less than 4 people seated
      abort;  //No solution possible (at least, with the decisions taken so far)

  //All tables filled with players, prepare for the next round.
  for each table T:
    for each player X on T:
      Register on X that he has sat with each of the other 3 players at T
    Unseat all players at T

此方式，对于单轮的算法尝试所有玩家至多一次每个表，以便在单次运行的尝试至多3 * T * N次它终止之前容纳一个播放器（具有或不具有一个溶液） 。换言之，单次运行应该快速完成pretty的。

This way, for a single round the algorithm tries all players at most once per table, so that a single run attempts at most 3*T*N times to seat a player before it terminates (either with or without a solution). In other words, a single run should be done pretty quick.

需要注意的是，因为它仍然随机它是完全可以接受的执行与此相同的算法多次，因为它会尝试座位每一次的不同组合（使其成为一个所谓的拉斯维加斯算法）。

Note that, because it's still randomized it is perfectly acceptable to run this same algorithm multiple times, because it will attempt different combinations of seating every time (making it a so-called Las Vegas algorithm).

编辑2 ：屡试不爽该算法与5氏族各16名球员。一般情况下，大约需要400运行它找到的第一个解决方案之前，但总的运行时间仍然只有1秒左右。

Edit 2: Tried and tested this algorithm with 5 clans of 16 players each. Usually, it takes about 400 runs before it finds the first solution, but the total running time is still only about 1 second.

这篇关于分发球员表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！