3
$\begingroup$

OK, I'm not sure if I can explain this:

  • I have 12 players
  • I want that each player play 3 times
  • Each game is of 3 vs 3 players
  • In each game each player plays with 2 different team members (no duplicate team members in the 3 matches)

I want that during the tournament each player avoid having more than one duplicate opponent (or none if possible)

Can you help me?

$\endgroup$
  • $\begingroup$ Have you tried just writing out a tournament? As each player has only 6 team members and 9 opponents, it seems like it shouldn't be hard. Think of three rounds of two games each, where each player is in one game or the other. The restrictions may get hard, though. $\endgroup$ – Ross Millikan Jul 25 '13 at 16:31
  • $\begingroup$ @RossMillikan That's what I did... and that was the problem that I found. $\endgroup$ – Leizar Azariel W. Jul 25 '13 at 16:56
  • $\begingroup$ @RossMillikan: Unless you come up with some better way to decide which matches to take: Yes, they are hard. I chose to implement this with Python and I just counted the number of times it ended up with some combination of matches that fulfill all restrictions, but you can't get 6 matches. It were 3090 failed tries! $\endgroup$ – Martin Thoma Jul 26 '13 at 7:22
  • $\begingroup$ By "no duplicate team members in the 3 matches", do you mean that (for instance) if my teammates in some match are the two players A and B, then in the next match I can't have teammates A and C, because A is duplicate? $\endgroup$ – ShreevatsaR Jul 26 '13 at 9:07
  • $\begingroup$ @LeizarAzarielW. What ShreevatsR wants to know is if you mean: a) $\forall t_i, t_j \in \text{List of all 12 teams}: i \neq j \Rightarrow t_i \cap t_j = \emptyset$ or b) $\forall t_i, t_j \in \text{List of all 12 teams}: i \neq j \Rightarrow t_i \neq t_j$. a) Means, once you've played with a guy, you'll not play with him again. b) means, there is never the same team in any match. So a) is much stronger than b) as $a) \Rightarrow b)$. For my solution, I thought you want a). $\endgroup$ – Martin Thoma Jul 26 '13 at 9:21
5
$\begingroup$

Restrictions

  • (I) 12 players
  • (II) Each player has to play exactly 3 times
  • (III) Each game is of 3 vs 3 players
  • (IV) In each game each player plays with 2 different team members (no duplicate team members in the 3 matches). So: $\forall t_i, t_j \in \text{List of all 12 teams}: i \neq j \Rightarrow t_i \cap t_j = \emptyset$
  • (V) Every player plays at most 1 time more than once against the same opponent player
  • (VI) No player plays against himself

Some thoughts first:

  • (VII) You need exactly $\underbrace{12}_{(I)} \cdot \frac{\overbrace{3}^{(II)}}{\underbrace{6}_{(III)}} = \frac{36}{6} = 6$ matches

  • (I), (III) and (VI) $\Rightarrow$ There are $\binom{12}{3} \cdot \binom{9}{3} = 220 \cdot 84 = 18480$ possbile matches

  • (VII) and above $\Rightarrow$ There are $\binom{18480}{6} = 55274746326873815880600 \approx 5.5 \cdot 10^{22}$ possible games
  • $\Rightarrow$ numbers are way too big to brute force. But maybe we can use (IV), (V) to reduce numbers.

Code

If you relax (V) to twice I found a solution with the following script:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def existsDuplicateTeamMember(games, team):
    for i in range(3):
        for j in range(i+1,3):
            for game in games:
                if (team[i] in game[0] and team[j] in game[0]) or \
                   (team[i] in game[1] and team[j] in game[1]):
                    return True
    return False

def isMaximumGamesReached(playerCount, team):
    for player in team:
        if playerCount[player] >= 3:
            return True
    return False

def isConditionBroken(games, playerCount, team):
    return isMaximumGamesReached(playerCount, team) or \
       existsDuplicateTeamMember(games, team)

def willGetDuplicateOpponents(opponents, team1, team2):
    for player in team1:
        newDuplicates = 0
        for opponent in team2:
            if opponents[player][opponent] >= 1:
                newDuplicates += 1
        if sum(map(lambda k: k-1,filter(lambda k: k>1, opponents[player].values()))) + newDuplicates > 1:
            return True
    for player in team2:
        newDuplicates = 0
        for opponent in team1:
            if opponents[player][opponent] >= 1:
                newDuplicates += 1
        if sum(map(lambda k: k-1,filter(lambda k: k>1, opponents[player].values()))) + newDuplicates > 1:
            return True
    return False

def updateDuplicateOpponents(opponents, team1, team2):
    for player in team1:
        newDuplicates = 0
        for opponent in team2:
            opponents[player][opponent] += 1
    for player in team2:
        newDuplicates = 0
        for opponent in team1:
            opponents[player][opponent] += 1
    return opponents

def printGamesNice(games):
    for game in games:
        print(str(game[0]) + " vs. " + str(game[1]))

def printNiceOpponentMatrix(players, opponents):
    line = "  "
    for player in players:
        line += player + " "
    line += "| Duplicates"
    print(line)

    for player1 in players:
        line = player1 + " "
        for player2 in players:
            line += str(opponents[player1][player2]) + " "
        line += "|" + str(sum(map(lambda k: k-1,filter(lambda k: k>1, opponents[player1].values()))))
        print line

def game(players, playerCount, opponents, games = []):
    from itertools import combinations
    from collections import defaultdict
    from copy import deepcopy
    if playerCount == None:
        playerCount = defaultdict(int)

    if opponents == None:
        opponents = {}
        for player1 in players:
            opponents[player1] = {}
            for player2 in players:
                opponents[player1][player2] = 0

    for team1 in combinations(players, 3):
        if isConditionBroken(games, playerCount, team1):
            continue

        for team2 in combinations(players, 3):
            if isConditionBroken(games, playerCount, team1):
                continue
            if isConditionBroken(games, playerCount, team2):
                continue
            if willGetDuplicateOpponents(opponents, team1, team2):
                continue
            # A player should not be forced to play against 
            # himself
            if len(set(team1).intersection(set(team2))) > 0:
                continue

            # copy current matches and add new match
            gameCopy = deepcopy(games)
            gameCopy.append([team1, team2])
            # copy oppenents and adjust that
            opponentsCopy = deepcopy(opponents)
            opponentsCopy = updateDuplicateOpponents(opponentsCopy, team1, team2)
            # copy playerCount and adjust
            playerCountCopy = deepcopy(playerCount)
            for player in (team1+team2):
                playerCountCopy[player] += 1
            # descend in depth-first-search tree
            returned = game(players, playerCountCopy, opponentsCopy, gameCopy)
            if returned != None:
                return returned
            continue

    if len(games) == 5:
        printGamesNice(games)
        print("#"*20)

    if len(games) == 6:
        printNiceOpponentMatrix(players, opponents)
        return games
    else:
        return None

if __name__ == "__main__":
    players = map(chr, range(65, 65+12))
    games = game(players, None, None)
    printGamesNice(games)

Ideas in the code

Well ... pretty straight forward. You basically try every combination. It's implemented as a depth-first-search.

I make use of itertools.combinations, set and defaultdict. I love Python ♥

Solution

  A B C D E F G H I J K L | Duplicates
A 0 1 1 1 2 2 0 1 0 1 0 0 |2
B 1 0 0 2 1 1 2 0 0 1 0 1 |2
C 1 0 0 1 2 1 0 0 2 1 1 0 |2
D 1 2 1 0 1 0 1 1 0 1 0 1 |1
E 2 1 2 1 0 1 1 0 0 1 0 0 |2
F 2 1 1 0 1 0 1 1 1 0 1 0 |1
G 0 2 0 1 1 1 0 1 1 0 1 1 |1
H 1 0 0 1 0 1 1 0 2 1 1 1 |1
I 0 0 2 0 0 1 1 2 0 1 1 1 |2
J 1 1 1 1 1 0 0 1 1 0 1 1 |0
K 0 0 1 0 0 1 1 1 1 1 0 3 |2
L 0 1 0 1 0 0 1 1 1 1 3 0 |2
('A', 'B', 'C') vs. ('D', 'E', 'F')
('A', 'D', 'G') vs. ('B', 'E', 'H')
('A', 'E', 'I') vs. ('C', 'F', 'J')
('B', 'D', 'K') vs. ('G', 'J', 'L')
('C', 'H', 'L') vs. ('I', 'J', 'K')
('F', 'I', 'L') vs. ('G', 'H', 'K')

At least there are at maximum two duplicate opponents. My script currently tries to find a solution with at most one duplicate opponent. It checks all combinations in alphabetical order. Currently it checked:

1. ('A', 'B', 'C') vs. ('D', 'E', 'F')
2. ('A', 'D', 'G') vs. ('B', 'E', 'H')
3. ('A', 'F', 'J') vs. ('C', 'G', 'I')
4. ('H', 'I', 'J') vs. ('B', 'K', 'L')
5. ('F', 'H', 'L') vs. ('E', 'J', 'K')

I guess as soon as the 3. match gets 'B' in the first position we can be sure that there is no possibility to avoid more than one duplicate opponent.

edit:

The script just checked:

('A', 'B', 'C') vs. ('D', 'E', 'F')
('A', 'D', 'G') vs. ('B', 'E', 'H')
('B', 'D', 'I') vs. ('J', 'K', 'L')
('A', 'I', 'L') vs. ('C', 'G', 'J')
('F', 'H', 'K') vs. ('C', 'E', 'L')

after some hours of execution. So I guess (no proof :-( ) there is no way to get a solution with only one duplicate opponent.

$\endgroup$
  • 1
    $\begingroup$ While this didn't lead to an optimal answer, it definitely deserves more up-votes $\endgroup$ – jameselmore Jul 26 '13 at 21:34
1
$\begingroup$

Here's a near-solution using the Z3 SMT solver.

We represent our search space as a $12 \times 3 \times 2 \times 2$ array of 1's and 0's. $X[p][r][g][t] = 1$ if player $p$ is on team $t$ of game $g$ in round $r$, and otherwise equals $0$. We then require the following constraints:

  • Each player plays once per round.
  • Each team has exactly three players.
  • No two players play together (on the same team) more than once.

We'd like to also satisfy:

  • Each player has at least eight distinct opponents.

But I've had the solver running for a while with that constraint and haven't gotten a solution back yet. So we settle for:

  • Each player has at least seven distinct opponents.
  • No two players play against each other more than twice.

Which gives this solution:

  • Round 0, game 0: [1, 9, 10] vs. [0, 4, 6]
  • Round 0, game 1: [2, 3, 8] vs. [5, 7, 11]
  • Round 1, game 0: [0, 7, 10] vs. [2, 5, 6]
  • Round 1, game 1: [8, 9, 11] vs. [1, 3, 4]
  • Round 2, game 0: [4, 5, 9] vs. [1, 2, 7]
  • Round 2, game 1: [6, 8, 10] vs. [0, 3, 11]

Here's the source code:

from z3 import *

X = [ [ [ [ Int("x_%s_%s_%s_%s" % (p,r,g,t)) 
            for t in range(2) ]
          for g in range(2) ]
        for r in range(3) ]
      for p in range(12) ]

# Each cell is 0 or 1
bits_c = [ Or(X[p][r][g][t] == 0, X[p][r][g][t] == 1)
           for t in range(2)
           for g in range(2)
           for r in range(3)
           for p in range(12) ]

# Each player plays once per round.
distinct_c = [ Sum([ X[p][r][g][t] 
               for t in range(2) for g in range(2) ]) == 1
               for r in range(3) for p in range(12) ]


# Each team has three players.
teamsize_c = [ Sum([ X[p][r][g][t] 
                     for p in range(12) ]) == 3
               for g in range(2)
               for r in range(3)
               for t in range(2) ]

# No two players play together more than once.
teammates_c = [ Sum( [X[p][r][g][t] * X[q][r][g][t]
                      for t in range(2)
                      for g in range(2)
                      for r in range(3)]) <= 1
                for p in range(12)
                for q in range(p) ]

# No two players play against each other more than twice.
opponents2_c = [ Sum( [X[p][r][g][0] * X[q][r][g][1] + 
                      X[p][r][g][1] * X[q][r][g][0]
                      for g in range(2)
                      for r in range(3)]) <= 2
                for p in range(12)
                for q in range(p) ]


# Each player has at least seven opponents.
opponents7_c = [ Sum( [ If(X[p][0][0][0] * X[q][0][0][1] +
                           X[p][0][0][1] * X[q][0][0][0] +
                           X[p][0][1][0] * X[q][0][1][1] +
                           X[p][0][1][1] * X[q][0][1][0] +
                           X[p][1][0][0] * X[q][1][0][1] +
                           X[p][1][0][1] * X[q][1][0][0] +
                           X[p][1][1][0] * X[q][1][1][1] +
                           X[p][1][1][1] * X[q][1][1][0] +
                           X[p][2][0][0] * X[q][2][0][1] +
                           X[p][2][0][1] * X[q][2][0][0] +
                           X[p][2][1][0] * X[q][2][1][1] +
                           X[p][2][1][1] * X[q][2][1][0] > 0,
                           1, 0) for q in range(12)]) >= 7
                 for p in range(12) ]

s = Solver()
s.add(bits_c + distinct_c + teamsize_c + 
      teammates_c + opponents2_c + opponents7_c)
if s.check() == sat:
    m = s.model()
    r = [ [ p for p in range(12)
            if str(m.evaluate(X[p][r][g][t])) == "1" ]
          for r in range(3)
          for g in range(2)
          for t in range(2)
          ]
    print_matrix(r)
else:
    print "no solution"
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.