Find ternary relationships with no duplicates for game scheduling algorithm

Question

I'm working on assigning groups in Python using rules.

You could think about it like building a season for a three player based game.

Each player needs to face the other players on the list exactly once.

So suppose I have this list:

 players = ['a','b','c','d','e','f','g','h','i','j','k']

Here's the expected output if we start with 'a':

game schedule for a:

game 1 = a, b, c

game 2 = a, d, e

game 3 = a, f, g

game 4 = a, h, i

game 5 = a, j, k

I'll need a schedule like that above for each player.

What I've got right now gets me 45 combinations for player 'a'... trying to figure out how to whittle it down:

 players = ['a','b','c','d','e','f','g','h','i','j','k']
 
 from itertools import combinations
 
 num = 3
 
 all_games = list(combinations(players, num))
 
 a_s = []
 
 for i in all_games:
 if 'a' in i:
 a_s.append(i)

I'm just not sure how to build in the condition I want.

I suppose I could (in pseudo code):

 create a list without the player I want:
 
 player = ['a']
 opponents = ['b','c','d','e','f','g','h','i','j','k']
 
 extract/get every 2 elements from the list
 
 add player a to the extracted opponent pairs

But I don't know if that's close to the best way to solve this.

• iBeMeltin: Can you provide an example of what you want your output would look like? I am not sure I understand what you are asking
• postcardfiction: @iBeMeltin yes, there's an output in there. If you think of the elements in the list as players/teams that need to be scheduled: 'a' needs to face 'b' and 'c', etc. I'm expecting to be able to give 'a' a schedule of 5 games: game 1 = a, b, c game 2 = a, d, e game 3 = a, f, g game 4 = a, h, i game 5 = a, j, k I can't schedule this game: (a, b, e) because 'a' has already been scheduled against 'b' in game 1. The output could be a dictionary like 'game 1': (a,b,c) etc. Or just a list of the right tuples, or a list of lists.
• Chris: Look up Steiner Triple System. There are some rules about the number of players required to ensure everyone can meet once, with some decisions to make if there players who get left out. math.stackexchange.com/questions/3238655/…
• Kelly Bundy: How is this supposed to be possible? You have 55 pairs, each game covers 3 pairs, and 55 isn't divisible by 3.
• postcardfiction: @Chris Thanks! This is exactly the right direction and I have never heard of the Steiner Triple System before!

Answer 1

Here is a way to solve this problem; using for loops.

players = ['a','b','c','d','e','f','g','h','i','j','k']
player_games = {}
for opponent in range(1, len(players), 2):
 player_games[f"game {int((opponent + 1) / 2)}"] = ["a", players[opponent], players[opponent+1]] # Replace "a" with your criteria of finding the player
print(player_games)

Output:

{'game 1': ['a', 'b', 'c'], 'game 2': ['a', 'd', 'e'], 'game 3': ['a', 'f', 'g'], 'game 4': ['a', 'h', 'i'], 'game 5': ['a', 'j', 'k']}

This code works assuming you have an odd amount of players (even number after excluding the player.). If you just want something like [a,l] in the end, here is a tweaked version of the code:

players = ['a','b','c','d','e','f','g','h','i','j','k',"l"]
player_games = {}
for opponent in range(1, len(players), 2):
 try:
 player_games[f"game {int((opponent + 1) / 2)}"] = ["a", players[opponent], players[opponent+1]]
 except IndexError:
 player_games[f"game {int((opponent + 1) / 2)}"] = ["a", players[opponent]]
print(player_games)

we just add a try..except block to catch an IndexError which we get with the above code.

Output:

{'game 1': ['a', 'b', 'c'], 'game 2': ['a', 'd', 'e'], 'game 3': ['a', 'f', 'g'], 'game 4': ['a', 'h', 'i'], 'game 5': ['a', 'j', 'k'], 'game 6': ['a', 'l']}

Here is a short explanation for how this code works.

We use a range to include every other letter's index (skip the first one since that is the player). We then include the current index and the index after the current one in a list. For example, ['b', 'c'] and then squash an a at the front: ['a', 'b', 'c']

The key increases by one for every iteration, but we are using range with 2 step, meaning we have to divide the opponent by two to get the game number. But, since we started at 1, we also have to add one.

• postcardfiction: this is very cool thank you! I can extend this to get a schedule of games for all players.
• Diego Ferruchelli: A key question: if you have [a, b, c], etc (as in the proposed and accepted solution), can you also have [b, a, c]? Because the hard part of the algorithm is avoiding the repetition of the pairs [a, b], [a, c] and [b, c] (all of them present in both "games"). This is even harder if you want all players to participate in the same number of games overall.
• Diego Ferruchelli: In the other hand, it's much easier if you accept something like [a, [b, c]] and [b, [a, c]] as two different "games" (separating a "leader" in each "game", and applying the "avoid repetition" rule inside all games leaded by "a", then inside all games leaded by "b", etc).
• postcardfiction: Right. I've ended up thinking of the "leader" as the "umpire" or "referee" for the game. Each player needs to referee the same number of games and to play the same number of games. I can get it to work with 6 players: each player referees 5 games, and plays in 10 games. I dropped the requirement to have each player face the other players exactly once. Although perhaps that could still be worked out, it turned out to be unnecessary - what mattered was them playing an equal number of games.
• Kelly Bundy: @postcardfiction How?
• postcardfiction: You were right to point out the difficulties with the initial problem. I adjusted the number of players down to 6 and shifted the way to think about the situation a little: Construe the players as having one of 2 capacities in a game: player or umpire. It turns out that what is needed here is for each player to umpire 5 games. And in season for each player to play in 10 games. A player can never umpire a game in which they are a player-only. 1) umpire: a, players[b,c]; 2) umpire: a, players[c,d], 3) umpire: a, players[d,e], etc..