Volleyball Player Combination

Question

Some Background:
In volleyball, players play in pools to determine rankings. Teams are pairs of players. Matches are a pair of players vs another pair of players. For this example, lets assume there is only one court the match can be played on and when a player isn't playing, they are sitting/waiting. The number of players in a pool will be between 4 and 7. If there are 8 players in a pool, they would just break it into 2 pools of 4 instead.

I want to calculate the least number of matches in order for each player to play with every other player.

For instance, a 4 player pool will have the following teams:

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

Outputs:

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

and the number of matches:

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

Outputs:

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

Which is correct but this algorithm breaks when I add a 5th player to the pool:

((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))

The teams are duplicated a number of times.

I tried to keep a list of teams that play but that algorithm turns out to be greedy. By this I mean when it gets to the (1,5) team, all the other teams [(2,3),(2,4),(3,4)] have already played and (1,5) never gets to play.

What I'm looking for:

((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)

Would it be easier to just calculate this by hand for each pool size or can this be done easily in python?

Thanks for the help!

---

Edit: Removed Python tag. Any language will suffice and I can convert it to Python.

Answer 1

Executive summary:

• In spite of its similarity to the NP-complete minimum set cover problem, this question is far from intractable. In particular -- and quite unlike minimum set cover -- we know a non-trivial best possible answer in advance.

• That answer is the number of teams divided by 2 (plus 1 when the N of teams is odd). We can never do better than that.

• Because of the structure of the problem, there are many acceptable solutions that achieve the best possible answer. You can stumble across them using a basic randomized greedy algorithm. As the N of teams grows large, your first random attempt is almost always successful.

• This approach is fast even for large numbers of teams (for example, just a couple of seconds for 1000 teams).

Details:

You can use the formula for k-combinations to determine the number of teams required so that every player is paired with every other player (with 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

What about the minimum number of matches? I think it's simply n_teams divided by 2 (with some padding to handle an odd number of teams).

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

I don't have a rigorous proof for this, but the intuition seems sound. Each time you add a new player, you can think of that as an additional constraint: you've just added one more player who cannot appear on both sides of a given match. At the same time, that new player generates a bunch of new team combinations. Those new teams are like anti-constraints: their presence makes it easier to form valid matches.

As you can see from the formula and data table above, the constraints (n) grow in linear fashion, but the anti-constraints (n_teams) grow much faster.

If that's true, you don't need a smart algorithm to solve the problem: the greediest, most brain-dead algorithm will work fine. Match the teams randomly (but validly), and if your first attempt fails, just try again. As the number of teams grows larger, you'll rarely fail on the first attempt.

There might be a better way to implement that idea, but here's an illustration that generates the teams and matches and confirms the assertions implied above.

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()

A sample of output. Notice how the number of calls very quickly tends toward 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}

Answer 2

You can express this as a set-covering problem. With 4 players, take the set of all (unordered) pairs of players:

PP := {{0,1}, {0,2}, {0,3}, {1,2}, {1,3}, {2,3}}

A possible match is an unordered pair of these pairs such that you don't have the same player on both sides. Here, the possible matches are:

M := {{{0,1},{2,3}}, {{0,2},{1,3}}, {{0,3},{1,2}}}

Your problem is now that you want to find the smallest subset of this set such that its union is the set of all player-pairs, PP.

This is an instance of the minimum set cover problem which is NP complete. Perhaps restricting the sets to pairs gives an easier solution, but it won't be surprising if not.

Since you're limiting to smallish sets, it's quite viable to just to solve it by brute-force.

We know that it'll take at least ceil(N * (N-1) / 4) matches (since there's N * (N-1) / 2 different pairs, and each match can cover at most 2 new pairs). That gives us an algorithm.

import itertools

def mincover(n):
    pairs = set(map(tuple, itertools.combinations(range(n), 2)))
    matches = itertools.combinations(pairs, 2)
    matches = [m for m in matches if not(set(m[0]) & set(m[1]))]
    for subset_size in xrange((len(pairs) + 1) // 2, len(pairs) + 1):
        for subset in itertools.combinations(matches, subset_size):
            cover = set()
            for s in subset: cover |= set(s)
            if cover == pairs:
                return subset

for i in xrange(4, 8):
    print i, mincover(i)

It's quite slow, especially for 6 and 7 players. This could be improved a bit by a hand-coded search that doesn't consider matches that don't add new player-pairs, and by using symmetry and always including {{0,1}, {2,3}}.