algorithm - Volley 运动员组合

Question

一些背景:
在 Volley 运动中，运动员在台球中比赛以确定排名。团队是成对的玩家。比赛是一对球员对另一对球员。对于这个例子，假设只有一个球场可以进行比赛，当一名球员没有比赛时，他们正在坐着/等待。一个池中的玩家数量将在 4 到 7 之间。如果一个池中有 8 个玩家，他们只会将其分成 2 个池，每池 4 个。

我想计算每个玩家与其他玩家一起玩的最少匹配次数。

例如，一个 4 人玩家池将有以下队伍:

import itertools
players = [1,2,3,4]
teams = [t for t in itertools.combinations(players,2)]
print 'teams:'
for t in teams:
    print t

输出:

teams:
(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)

和匹配的数量:

matches = []
for match in itertools.combinations(teams,2):
    # A player cannot be on both teams at the same time
    if set(match[0]) & set(match[1]) == set():
        matches.append(match)

for match in matches:
    print match

输出:

((1, 2), (3, 4))
((1, 3), (2, 4))
((1, 4), (2, 3))

这是正确的，但是当我将第 5 个玩家添加到池中时，此算法会中断:

((1, 2), (3, 4))
((1, 2), (3, 5))
((1, 2), (4, 5))
((1, 3), (2, 4))
((1, 3), (2, 5))
((1, 3), (4, 5))
((1, 4), (2, 3))
((1, 4), (2, 5))
((1, 4), (3, 5))
((1, 5), (2, 3))
((1, 5), (2, 4))
((1, 5), (3, 4))
((2, 3), (4, 5))
((2, 4), (3, 5))
((2, 5), (3, 4))

团队重复了很多次。

我试图保留一份参加比赛的球队名单，但结果证明该算法是贪婪的。我的意思是当它到达 (1,5) 队时，所有其他队 [(2,3),(2,4),(3,4)] 已经玩过并且 (1,5) 永远不会玩。

我在找什么:

((1,2), (3,4)) (player 5 waits)
((1,3), (2,5)) (player 4 waits)
((1,4), (3,5)) (player 2 waits)
((1,5), (4,2)) (player 3 waits)
((2,3), (4,5)) (player 1 waits)

对于每个池大小手动计算这个是否更容易，或者这可以在 python 中轻松完成吗？

感谢您的帮助!

---

编辑:删除了 Python 标签。任何语言都可以，我可以将其转换为 Python。

Answer 1

执行摘要:

• 尽管它与 NP 完全最小集覆盖问题相似，但这个问题远非难解。特别是——与最小集覆盖完全不同——我们提前知道了一个非平凡的最佳可能答案。

• 答案是团队数除以 2(当团队数为奇数时加 1)。我们永远不会做得比这更好。

• 由于问题的结构，有许多可接受的解决方案来实现最佳答案。您可以使用基本的随机贪婪算法偶然发现它们。随着团队的 N 变大，您的第一次随机尝试几乎总是成功。

• 即使对于大量团队，这种方法也很快(例如，1000 个团队只需几秒钟)。

详细信息:

您可以使用 k 组合公式来确定所需的团队数量，以便每个玩家都与其他每个玩家配对(k = 2)。

n_teams = n! / ( (n - k)! k! )

n     n_teams
--    --------
4     6
5     10
6     15
7     21
8     28
9     36
10    45
11    55      # n_teams always equals the sum of values in previous row

最小匹配数是多少？我认为这只是 n_teams 除以 2(用一些填充来处理奇数个团队)。

min_n_matches = (n_teams + (n_teams % 2)) / 2

对此我没有严格的证明，但直觉似乎是正确的。每次添加新玩家时，您都可以将其视为额外的约束:您只是添加了一个不能同时出现在给定比赛双方的玩家。同时，那个新玩家产生了一堆新的团队组合。这些新团队就像反约束:他们的存在使得形成有效匹配变得更容易。

从上面的公式和数据表可以看出，约束(n)以线性方式增长，但反约束(n_teams)增长得更快.

如果那是真的，您就不需要聪明的算法来解决问题:最贪婪、最脑残的算法也能正常工作。随机(但有效)匹配团队，如果您的第一次尝试失败，请重试。随着团队数量的增加，第一次尝试很少会失败。

可能有更好的方法来实现这个想法，但这里有一个生成团队和比赛的例子，并证实了上面暗示的断言。

import sys
import itertools
import random

def main():
    maxN = int(sys.argv[1])
    for n in range(4, maxN + 1):
        run_scenario(n)

def run_scenario(n):
    # Takes n of players.
    # Generates matches and confirms our expectations.
    k = 2
    players = list(range(1, n + 1))
    teams   = list(set(t) for t in itertools.combinations(players, k))

    # Create the matches, and count how many attempts are needed.
    n_calls = 0
    matches = None
    while matches is None:
        matches = create_matches(teams)
        n_calls += 1

    # Print some info.
    print dict(
        n       = n,
        teams   = len(teams),
        matches = len(matches),
        n_calls = n_calls,
    )

    # Confirm expected N of matches and that all matches are valid.
    T = len(teams)
    assert len(matches) == (T + (T % 2)) / 2
    for t1, t2 in matches:
        assert t1 & t2 == set()

def create_matches(teams):
    # Get a shuffled copy of the list of teams.
    ts = list(teams)
    random.shuffle(ts)

    # Create the matches, greedily.
    matches = []
    while ts:
        # Grab the last team and the first valid opponent.
        t1 = ts.pop()
        t2 = get_opponent(t1, ts)
        # If we did not get a valid opponent and if there are still
        # teams remaining, the greedy matching failed.
        # Otherwise, we must be dealing with an odd N of teams.
        # In that case, pair up the last team with any valid opponent.
        if t2 is None:
            if ts: return None
            else:  t2 = get_opponent(t1, list(teams))
        matches.append((t1, t2))

    return matches

def get_opponent(t1, ts):
    # Takes a team and a list of teams.
    # Search list (from the end) until it finds a valid opponent.
    # Removes opponent from list and returns it.
    for i in xrange(len(ts) - 1, -1, -1):
        if not t1 & ts[i]:
            return ts.pop(i)
    return None

main()

输出样本。请注意调用次数如何很快趋向于 1。

> python volleyball_matches.py 100
{'matches': 3, 'n_calls': 1, 'teams': 6, 'n': 4}
{'matches': 5, 'n_calls': 7, 'teams': 10, 'n': 5}
{'matches': 8, 'n_calls': 1, 'teams': 15, 'n': 6}
{'matches': 11, 'n_calls': 1, 'teams': 21, 'n': 7}
{'matches': 14, 'n_calls': 4, 'teams': 28, 'n': 8}
{'matches': 18, 'n_calls': 1, 'teams': 36, 'n': 9}
{'matches': 23, 'n_calls': 1, 'teams': 45, 'n': 10}
{'matches': 28, 'n_calls': 1, 'teams': 55, 'n': 11}
{'matches': 33, 'n_calls': 1, 'teams': 66, 'n': 12}
...
{'matches': 2186, 'n_calls': 1, 'teams': 4371, 'n': 94}
{'matches': 2233, 'n_calls': 1, 'teams': 4465, 'n': 95}
{'matches': 2280, 'n_calls': 1, 'teams': 4560, 'n': 96}
{'matches': 2328, 'n_calls': 1, 'teams': 4656, 'n': 97}
{'matches': 2377, 'n_calls': 1, 'teams': 4753, 'n': 98}
{'matches': 2426, 'n_calls': 1, 'teams': 4851, 'n': 99}
{'matches': 2475, 'n_calls': 1, 'teams': 4950, 'n': 100}