CODEWITHSUNDEEP
pythonalgorithmcombinatorics
m00nlightsh4dow
m00nlightsh4dow

Reputation: 317

Generate each possible match from N players and create N-1 groups of N/2 matches each

I'm trying to write a script that generates every possible 1v1 match from N players and then creates N-1 groups (days) of N/2 players, so that each day everyone plays and by the end of all N-1 days, each player will have played against all other players.

In my case:

I wrote the script below but it doesn't work very well. I generate each possible match using player_combinations(). Then, I iterate N-1 times to create N-1 groups (days). I make sure to only include a given player once in each day and, before moving on to the next day, I subtract day from combinations and clear day, so that I won't use the same match twice.

The problem is that, after running the script, not every group has the same number of participants and the total number of matches doesn't add up to the correct one (it's lower).

What should I do? Is there an easy way (perhaps with partitions, permutations, etc.) of solving this problem that I'm not seeing?

SCRIPT:

from itertools import combinations


def player_combinations(players):
    return [' - '.join(i) for i in combinations(players, 2)]


p = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L']

combinations = player_combinations(p)
day = []

for i in range(len(p)-1):
    for pair in combinations:
        if not any(pair.split(' - ')[0] in participants for participants in day) and not any(pair.split(' - ')[1] in participants for participants in day):
            day.append(pair)

    for participants in day:
        print(participants)
    print()

    for participants in day:
        if participants in combinations:
            combinations.remove(participants)

    day.clear()

Upvotes: 1

Views: 1253

Answers (2)

Horace
Horace

Reputation: 342

I have used the reference below to make a round robin type script for your example. This will pair up each player in a special way to ensure the least amount of rounds with all or almost all (in the case of odd number of players) players in each round

reference here: https://nrich.maths.org/1443

import math

def shuffle(players): # rotate the values in players so the last player is first and everyone else is shifted one down
    shuffled = list(players[-1])
    shuffled.extend(players[:-1])
    return shuffled

def pair_up_players(players, shuffled_players): # pair up the values in players, round robin style
    pairs = []
    idx_left_side_players = range(math.floor(len(shuffled_players)/2))
    for idx in idx_left_side_players:
        p1 = shuffled_players[idx]
        p2 = shuffled_players[-idx-1-len(shuffled_players)%2]
        pairs.append((p1, p2))

    # if even number of players, pair up the last shuffled player with the last player in players
    if len(players) % 2 == 0:
        p1 = shuffled_players[-1]
        p2 = players[-1]
        pairs.append((p1, p2))

    return pairs


players = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L']
num_players = len(players)
rounds_to_play = num_players - 1 + num_players%2
result = []

# we shuffle all or all but the last player depending if num_players is even or odd
if num_players % 2 == 0: # even, shuffle all players except for the last one, which is static
    shuffled_players = players[:-1]
else:
    shuffled_players = players # shuffle all players around

# loop the rounds
for round in range(rounds_to_play):
    print(shuffled_players)
    result.append(pair_up_players(players, shuffled_players))
    shuffled_players = shuffle(shuffled_players)

print(result)

Upvotes: 2

Dave
Dave

Reputation: 9085

This is answered here: https://math.stackexchange.com/questions/1477767/efficiently-partition-a-set-into-all-possible-unique-pair-combinations

The idea is to make a complete graph on N vertices, putting all but one vertex on a regular polygon, with one in the center. We then do an edge coloring s.t. each vertex is incident with each edge color exactly once. The colors then represent rounds of the tournament, with each colored edge representing a pairing of its end-vertices in that round.

Let's call the edges that include the central vertex "central edges". We form the coloring by:

  1. First using all colors (rounds) for the central edges.
  2. Then, coloring all edges perpendicular to a given central edge with the color of that central edge.

E.g., 12 vertices labeled 0-11, 11 rounds labeled 0-10, 'colors'.

  1. Treat vertex 11 as the central vertex.
  2. color the edge from 11 to i with color i.
  3. make pairings / color edges (mod(i-j,11),mod(i+j,11)) with color i, for j in {1,2,3,4,5}.

Round Pairings:

  1. (11,0), (10,1), (9,2), (8,3), (7,4), (6,5)
  2. (11,1), (0,2), (10,3), (9,4), (8,5), (7,6)
  3. (11,2), (1,3), (0,4), (10,5), (9,6), (8,7)
  4. (11,3), (2,4), (1,5), (0,6), (10,7), (9,8)
  5. (11,4), (3,5), (2,6), (1,7), (0,8), (10,9)
  6. (11,5), (4,6), (3,7), (2,8), (1,9), (0,10)
  7. (11,6), (5,7), (4,8), (3,9), (2,10), (1,0)
  8. (11,7), (6,8), (5,9), (4,10), (3,0), (2,1)
  9. (11,8), (7,9), (6,10), (5,0), (4,1), (3,2)
  10. (11,9), (8,10), (7,0), (6,1), (5,2), (4,3)
  11. (11,10), (9,0), (8,1), (7,2), (6,3), (5,4)

Upvotes: 1

Related Questions