3

I am using a proper binary tree to simulate a tournament bracket. It's preferred any competitors in the bracket that are teammates don't meet each other until the later rounds. What is an efficient method in which I can ensure that teammates in the bracket have as much distance as possible from each other? Are there any other data structures besides a tree that would be better for this purpose?

EDIT: There can be more than 2 teams represented in a bracket and there is no requirement to have an equal number of people from each team in a bracket. I intend to use this for individual sports where a person still has an affiliation with a team and we want to delay teammates facing each other until as late as possible.

3
  • 1
    There's a similar question at using-python-to-model-a-single-elimination-tournament which you may want to look at. As in randomA's answer, start by assuming they all meet in (semi/quarter)final, then in previous round, split them up into the two halves. Repeat until all separate. Jun 5, 2014 at 8:49
  • It's been a long time, but this sounds like something Balanced Incomplete Block Designs might be useful for - can anybody confirm or deny?
    – J Trana
    Jun 12, 2014 at 4:44
  • The algorithm is quite simple: make a list of all competitors, sorted by team. Make 2 buckets, now start filling putting alternating one from the list in 1 bucket and another in the other. Now repeat this exact process recursively for each bucket (which should still be sorted by team) done.
    – Pieter B
    Aug 4, 2014 at 7:08

4 Answers 4

9

Just sort the players by team and number them starting from 0, so e.g.

0(000)  T1a (team 1 player a)
1(001)  T1b
2(010)  T1c
3(011)  T2a
4(100)  T2b
5(101)  T3a
6(110)  T3b
7(111)  T3c

Then reverse the bits in each number to fill out your bracket sheet

0(000)  T1a\______
1(001)  T2b/      \_______
2(010)  T1c\______/       \
3(011)  T3b/               \________
4(100)  T1b\______         /
5(101)  T3a/      \_______/
6(110)  T2a\______/
7(111)  T3c/
4
  • Thanks. This seems to work well. What theories or principles did you use to come up with this answer? Mar 22, 2015 at 21:40
  • The binary number represents an address in the tree, starting from the root node. The first bit tells if you should go left (0) or right (1). The reversal of the digits is only necessary if you read from left to right; the important part is reading the least significant bit first. This puts players similar to each other down different subtrees (exactly the same way as in my answer, actually; just a different way of viewing the same solution). Oct 16, 2015 at 13:18
  • In practice, you start with an empty bracket table with the numbers interleaved: Oct 16, 2015 at 18:04
  • It doesn't work, for example two teams of 4 players, T1a-T1b-T1c-T1d-T2a-T2b-T2c-T2d. The first pair is T1a/T2a
    – aprencai
    Nov 29, 2021 at 11:58
1

Let's suppose that the leaf nodes of your tree are numbered 0..n-1 where n is the total number of players. These numbers would be assigned via depth-first search. That would result in nodes 0 and 1 having a common parent, and 2 and 3 having a common parent. Parents of these parents will have a common parent and so on.

Now, let's also assume that you have m teams, each with n/m players, you could assign players numbers in round-robin fashion such that the players from team i are numbered i, n/m+i, n/m*2+i, n/m*3+i, ...

Once that happens, you distribute them across the leaf nodes of your tree and that should maximize the distance between them.

Example:
If no. of players = 16, no. of teams = 4.
Team 0 players = 0, 4,  8, 12
Team 1 players = 1, 5,  9, 13
Team 2 players = 2, 6, 10, 14
Team 3 players = 3, 7, 11, 15

All of the players are equally distributed with as much distance as possible without sacrificing any other team's players' distances.

If the number of players are not the same on every team, then please do let know, I will take another attempt at it.

1
  • The number of competitors from each team in a bracket need not be the same. Aug 4, 2014 at 2:37
1

I hope this has a proof built into itself.

The main idea is to delay the meeting of 2 teammates as much as possible. So a greedy algorithm would work.

The most we can delay is in the final, then semi-final1, semi-final2, quarter-final1, etc... Save this ordered list of match-up in list L1.

Sort the list of players with same team all together at the beginning of the list. This is list L2

Pop a match-up from L1, pop out 2 players in the same team from L2, fill the players into any leaves of the empty branches of the match up just got from L1. [correction: after the first iteration of the loop, each match-up will only have one branch unfilled (with players of the same team), so we need to pop another match-up to fill the second player]. This will ensure maximum distance between 2 teammates.

Continue with new match-up until the match-up is the first round. Now we can no longer delay, so fill all players in any arbitrary way. This is quite abstract, but I am sure it has enough details to implement

2
  • There can be any number of teams and any number of competitors. There will almost always be more than 2 teams. Jun 5, 2014 at 15:36
  • 1
    Then you do similar thing but you need to make modification so that there are multiple L2 lists, each L2 list contains only players of one team. For each match-up from L1,you pull up to 2 players from each L2 list iteratively. If there is no leaf left, you have to pull new matchup from L1. This will require some serious proof though.
    – InformedA
    Jun 8, 2014 at 9:27
0
  1. Start at the root node (the final match) and the entire list of players.
  2. Partition the list into equal sized two lists so that people from the same team end up in different lists. You can do this by looping through the teams and put half of the players from that team into each of the two partitions.
  3. Recurse down the left subtree with the first list and the right subtree with the second list and do the same thing again in each subtree.

This will ensure that players from the same team are evenly distributed. If there are only two players from one team you are even guaranteed that they cannot meet each other until the final because they were immediately split into different subtrees.

You can make the partition function used in step 2 generic. Send it in as a function pointer and you can easily extend it to take into account things such as rank.

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.