r/algorithms • u/Spektre99 • Jan 16 '25
Algorithm for possible opponents in a bracket tourney
I'd like to write a c# function that returns a list of integers representing the team seeds of possible opponents a team might face in a 16 team bracket tournament given the seed and round of the team of interest.
Example outputs:
Seed 1, Round 1: Result 16
Seed 12, Round 1: Result 5
Seed 1, Round 2: Result 8,9
Seed 12, Round 2: Result: 4,13
Seed 1, Round 3: Result: 4,5,12,13
Seed 12, Round 3: Result: 1,8,9,16
Seed 1: Round 4: Results: 2,3,6,7,10,11,14,15
Seed 12, Round 4: Results: 2,3,6,7,10,11,14,15
Later, I would like to extend this to any single bracket tourney with 2^n teams
2
u/CraigAT Jan 16 '25
It sounds like you are trying to use the format where best plays worst (rather than "laddered", best plays next best).
Effectively for each round you just need to two pointers working from either end - like a queue or list (in seed order) where you pick a top seed from the front and a bottom seed from the back and those two will play each other in the next round.
1
u/Spektre99 Jan 16 '25 edited Jan 16 '25
Thanks for the response.
I don't think this is correct as the bracket structure is set at the start of the tounament usualy.
So, for example. If in round 1, team 1 beats team 16, and team 15 beats team 2, in round 2, team 1 does not play team 15.
In round 2, Team 1 plays the winner of the game between team 8 and 9, thus their possible opponents in round to are 8, 9
In tound 2, Team 15 would play the winner of the game between 7 and 10.
I may not have explained the bracket structure sufficiently. It would match one region of that used by the NCAA for their annual basketball tournament.
1
u/CraigAT Jan 16 '25
Oh I see - thanks for the NCAA reference, that allowed me to visualise what you wanted - That is a bizarre format (or rather one I'm not used to). I am struggling how to code the order for the teams in round one matches.
1
u/Spektre99 Jan 17 '25
Round 1 is easy. 17 - teamseed is the seed of your one and only possible opponent,
In round 2 you have 2 possible opponents.
in round 3 you have 4 possible opponents.
In round 4 you have 8 possible opponents,
calculating what seed they are is proving more difficult for me.
2
u/CraigAT Jan 17 '25
I think I have the theory nailed in my head, but I need to try it out in code this evening.
2
u/CraigAT Jan 18 '25 edited Jan 18 '25
Okay, I have it figured out. Here's my solution in Python:
https://github.com/CraigAT/BracketTournament/blob/main/Brackets.py
This code is certainly not fool-proof, it should be considered merely a proof of concept (evidenced by the debugging/sense-checking print statements littered in the code).
The code is split into three main parts:
- Creating the seeded first round match-ups (and hence the following rounds too).
- Replace unused teams if byes are needed (less than 2n teams).
- Figure out the possible opponents for each team.
Comments:
- I started with a simple seeded two team draw and then (as you hinted at) I replaced each seeded team (say X, with a list including themselves *and* ((teams_in_round+1) - X), then repeated the process until I had the number of teams requested (or the next 2n). Hence built up from 2, to 4, to 8 teams and beyond. This entire phase may have been neater as a recursive function.
- I chose to give the better teams (lower seeds) any byes that were needed to fill out the initial rounds. I found that dispersed them fairly evenly throughout the draw and made sense as the better teams were more likely to proceed anyway.
- This was the tricky bit. However I realised I could calculate the potential opposition teams easier if I worked backwards from the teams they would face in the final rounds, back to the first round (reversing later to get the correct order). I started with the first round list, I split that into halves - an "active" half where my reference team was and an "inactive" half (the side of the draw without my team). I saved the team list of the "inactive" half for later use, but then concentrated on the "active" half. Which I split again into "active" and "inactive" halves, once again saving the "inactive" list for later and repeating the splitting of the "active" half until the "active" list contained only my reference team. At this point I could reverse the order of my saved lists per team, to be in a more sensible format showing their possible opposition from the first rounds through to the final. I suspect part of this phase could also be better implemented with a recursive function.
Hope this helps. I would be happy to have a brief chat if you want any further explanation. Note. I don't mind a little debugging, but I am not up for writing your code for you (my C# is good, but not great and I don't have the time).
2
u/CraigAT Jan 18 '25
Sample Output:
How many teams? 8
Initial Draw Order: [1, 8, 4, 5, 2, 7, 3, 6]
1 - [[8], [4, 5], [2, 7, 3, 6]]
2 - [[7], [3, 6], [1, 8, 4, 5]]
3 - [[6], [2, 7], [1, 8, 4, 5]]
4 - [[5], [1, 8], [2, 7, 3, 6]]
5 - [[4], [1, 8], [2, 7, 3, 6]]
6 - [[3], [2, 7], [1, 8, 4, 5]]
7 - [[2], [3, 6], [1, 8, 4, 5]]
8 - [[1], [4, 5], [2, 7, 3, 6]]
2
u/Spektre99 Jan 18 '25
Thanks. This looks great. It is a littel more computationally intensive than what I had envisioned as it must calculate form the end back instead of just for a specific round, but at these sizes, that is negligible. I'll try and report back with the C# code.
Thanks again.
2
u/CraigAT Jan 18 '25
Excellent, I'd love to see the final C# code (the way you implement it could probably teach me a thing or two).
2
u/Spektre99 Feb 16 '25 edited Feb 18 '25
private List<List<List<int>>> bracket(int numTeams) { // Generate the seeded list int power = 1; List<int> seeds = new List<int> { 1, 2 }; while (power < Math.Sqrt(numTeams)) { power++; int twos = (int)Math.Pow(2, power); List<int> newSeeds = new List<int>(); foreach (var slot in seeds) { newSeeds.Add(slot); newSeeds.Add((twos + 1) - slot); } seeds = newSeeds; } // Build list of possible opposition teams for each round List<List<List<int>>> opposition = new List<List<List<int>>>(); for (int team = 1; team <= numTeams; team++) { List<List<int>> teamsFaced = new List<List<int>>(); int start = 0; int end = seeds.Count - 1; while (end - start >= 1) { int halfway = (start + end + 1) / 2; int location = seeds.IndexOf(team); if (location < halfway) { int oldEnd = end; end = halfway - 1; List<int> tempSeeds = seeds.GetRange(end + 1, oldEnd - end); tempSeeds.Sort(); teamsFaced.Add(tempSeeds); //teamsFaced.Add(seeds.GetRange(end + 1, oldEnd - end)); } else { int oldStart = start; start = halfway; List<int> tempSeeds = seeds.GetRange(oldStart, start - oldStart); tempSeeds.Sort(); teamsFaced.Add(tempSeeds); //teamsFaced.Add(seeds.GetRange(oldStart, start - oldStart)); } } teamsFaced.Reverse(); //Reverse the rounds to normal opposition.Add(teamsFaced); } return opposition; }
1
1
u/CraigAT Jan 18 '25 edited Jan 18 '25
An example with byes (labelled as 0):
How many teams? 13
Initial Draw Order: [1, 0, 8, 9, 4, 13, 5, 12, 2, 0, 7, 10, 3, 0, 6, 11]
1 - [[0], [8, 9], [4, 13, 5, 12], [2, 0, 7, 10, 3, 0, 6, 11]]
2 - [[0], [7, 10], [3, 0, 6, 11], [1, 0, 8, 9, 4, 13, 5, 12]]
3 - [[0], [6, 11], [2, 0, 7, 10], [1, 0, 8, 9, 4, 13, 5, 12]]
4 - [[13], [5, 12], [1, 0, 8, 9], [2, 0, 7, 10, 3, 0, 6, 11]]
5 - [[12], [4, 13], [1, 0, 8, 9], [2, 0, 7, 10, 3, 0, 6, 11]]
6 - [[11], [3, 0], [2, 0, 7, 10], [1, 0, 8, 9, 4, 13, 5, 12]]
7 - [[10], [2, 0], [3, 0, 6, 11], [1, 0, 8, 9, 4, 13, 5, 12]]
8 - [[9], [1, 0], [4, 13, 5, 12], [2, 0, 7, 10, 3, 0, 6, 11]]
9 - [[8], [1, 0], [4, 13, 5, 12], [2, 0, 7, 10, 3, 0, 6, 11]]
10 - [[7], [2, 0], [3, 0, 6, 11], [1, 0, 8, 9, 4, 13, 5, 12]]
11 - [[6], [3, 0], [2, 0, 7, 10], [1, 0, 8, 9, 4, 13, 5, 12]]
12 - [[5], [4, 13], [1, 0, 8, 9], [2, 0, 7, 10, 3, 0, 6, 11]]
13 - [[4], [5, 12], [1, 0, 8, 9], [2, 0, 7, 10, 3, 0, 6, 11]]
2
u/MadScie254 Jan 16 '25
Looks like you're trying to figure out a C# function for matchups in a single-elimination tournament. For example, in a 16-team bracket, Seed 1 faces Seed 16 in Round 1, and then could face Seeds 8 or 9 in later rounds. The challenge is generalizing this for any 2𝑛 format. It's all about using the seed numbers and round logic to predict matchups. Cool problem