9

EDIT: My question is not a duplicate as someone has marked. The other question is incorrect and does not even work.

I have tried a few ways to group the results of itertools.combinations and been unable to come up with the correct output. It is needed to create matches in a game. Every team needs to play every day, but only once. Teams need to play different teams on the following days until everyone has played everyone.

teams = [team 1, team 2, team 3, team 4]
print list(itertools.combinations(teams, 2))

the result:

[(team 1, team 2), (team 1, team 3), (team 1, team 4), (team 2, team 3), (team 2, team 4), (team 3, team 4)]

But what I need is to group them without any duplicate list items. example:

[
    [(team 1,team 2), (team 3,team 4)], #day 1
    [(team 1,team 3), (team 2,team 4)], #day 2
    [(team 1,team 4), (team 2,team 3)]  #day 3
]

Any tips would be appreciated, I feel like there's probably a simple one-liner to get this done.

Padraic Cunningham
  • 176,452
  • 29
  • 245
  • 321
Johnny Craig
  • 4,974
  • 2
  • 26
  • 27
  • How many teams are playing each day?.. Are they self determine which teams they play against each other or what you want ot acheive will determine it? – Richard Sep 02 '15 at 16:58
  • Each game has a different number of teams. Lowest is 2 teams, maximum is 128 teams. Im not sure I understand the second part of your question. I am trying to create all of the team matches, the players do not do it. – Johnny Craig Sep 02 '15 at 17:01
  • Its basically like knockout stages in any competition. Every team plays the other one once. Here our teams are `1`,`2`,`3`,`4` . right? – letsc Sep 02 '15 at 17:04
  • Correct. I should have probably named them as such. I will do that edit now. team 1, team 2, team 3, team 4 – Johnny Craig Sep 02 '15 at 17:04
  • It is a coincidence that only appears with four teams, when you add more teams you can no longer just grab matches from each end. – Johnny Craig Sep 02 '15 at 17:14
  • 2
    I think you will probably find a solution here http://stackoverflow.com/questions/11245746/league-fixture-generator-in-python/11246261#11246261 – gtlambert Sep 02 '15 at 17:14
  • That solution does not work as it is explained and the output doesn't match the answer. See my comment there. This question still needs a working answer – Johnny Craig Sep 02 '15 at 18:20
  • I would probably do something like `itertools.izip_longest(teams[::2], teams[1::2])` here after randomizing the order (say, `random.shuffle(teams)`). That doesn't quite match your expected output, as it only creates the matches for a single "day" and not multiple ones, but I'm not quite sure I follow how this is supposed to deal with eliminations. Don't you _have_ to run it each day after you determine which teams are still in? – Two-Bit Alchemist Sep 02 '15 at 18:45
  • All teams need to play each other one time, each team playing one game per day. If there are any eliminations, it won't happen until all teams have played each other once. So all matches need to be generated before the start so no matches are duplicated. If I want a duplicate match, I will just iterate through my list again. This is "normal season, not the "playoffs" – Johnny Craig Sep 02 '15 at 18:55
  • "all matches need to be generated before the start so no matches are duplicated" -- why can't you use something like the `izip_longest` I suggested then? (That will give you a list of 2-tuples which you can consider to be pairs of teams assigned to play, and if there are an odd number of teams one gets paired with `None`, which I suppose means they get a "bye" or whatever.) – Two-Bit Alchemist Sep 02 '15 at 19:26
  • I previously tried izip_longest, it only gave me one day of matches. I need all matches until all tams played each other. I have figured out a solution. I will post it as soon as I clean it up a bit. – Johnny Craig Sep 02 '15 at 19:54
  • @JohnnyCraig I guess it's moot if you've figured out a solution but I'm just trying to figure out what's different about the output of what I suggested and what you want/expect. I did something like this: `teams = list(range(1, 10)); random.shuffle(teams)`, and `izip_longest` as above gives similar to: `[(8, 4), (3, 2), (7, 9), (1, 6), (5, None)]` -- all teams paired, no duplicates. What do you need instead? – Two-Bit Alchemist Sep 02 '15 at 21:30
  • It needs an output for all games. not just one day, with no duplicates. i.e.: `week 1 matches: [('Team 1', 'Team 2'), ('Team 3', 'Team 4'), ('Team 5', 'Team 6'), ('Team 7', 'BYE')] week 2 matches: [('Team 1', 'Team 3'), ('Team 2', 'Team 4'), ('Team 5', 'Team 7'), ('Team 6', 'BYE')] ... etc week 3 matches: [('Team 1', 'Team 4'), ('Team 2', 'Team 3'), ('Team 5', 'BYE'), ('Team 6', 'Team 7')] week 4 matches: [('Team 1', 'Team 5'), ('Team 2', 'Team 6'), ('Team 3', 'Team 7'), ('Team 4', 'BYE')] week 5 matches: [('Team 1', 'Team 6'), ('Team 2', 'Team 5'), ('Team 3', 'BYE'), ('Team 4', 'Team 7')] – Johnny Craig Sep 02 '15 at 21:34
  • @Two-BitAlchemist, all teams should play each day (or get a bye for odd amount of teams) and all teams should play each other exactly once – Padraic Cunningham Sep 02 '15 at 21:36
  • 1
    Ohh, all teams should play each other exactly once _over the course of the season_. Now I get it. – Two-Bit Alchemist Sep 02 '15 at 21:43
  • 1
    To add to the confusion, its actually a 14 week season so I will add or splice my list accordingly. This is now working. Thanks for everyones time. – Johnny Craig Sep 02 '15 at 21:51

1 Answers1

4

An implementation using a collections.deque based on the Scheduling_algorithm in the linked question:

from collections import deque
from itertools import islice

def fixtures(teams):
    if len(teams) % 2:
        teams.append("Bye")

    ln = len(teams) // 2
    dq1, dq2 = deque(islice(teams, None, ln)), deque(islice(teams, ln, None))
    for _ in range(len(teams)-1):
        yield zip(dq1, dq2) # list(zip.. python3
        #  pop off first deque's left element to 
        # "fix one of the competitors in the first column"
        start = dq1.popleft() 
        # rotate the others clockwise one position
        # by swapping elements 
        dq1.appendleft(dq2.popleft())
        dq2.append(dq1.pop())
        # reattach first competitor
        dq1.appendleft(start)

Output:

In [37]: teams = ["team1", "team2", "team3", "team4"]

In [38]: list(fixtures(teams))
Out[38]: 
[[('team1', 'team3'), ('team2', 'team4')],
 [('team1', 'team4'), ('team3', 'team2')],
 [('team1', 'team2'), ('team4', 'team3')]]

In [39]: teams = ["team1", "team2", "team3", "team4","team5"]

In [40]: list(fixtures(teams))
Out[40]: 
[[('team1', 'team4'), ('team2', 'team5'), ('team3', 'Bye')],
 [('team1', 'team5'), ('team4', 'Bye'), ('team2', 'team3')],
 [('team1', 'Bye'), ('team5', 'team3'), ('team4', 'team2')],
 [('team1', 'team3'), ('Bye', 'team2'), ('team5', 'team4')],
 [('team1', 'team2'), ('team3', 'team4'), ('Bye', 'team5')]]
Padraic Cunningham
  • 176,452
  • 29
  • 245
  • 321