Algorithm for placement of 32 seeded players in a 128 person tournament

Question

I am trying to create a tennis tournament simulator, where the outcomes of the games are random (sort of). At Grand Slams there are 128 players, 32 of which are seeded. At the moment I am trying to place the seeds in the draw at the appropriate position. I have the generated strengths of the players according to a normal distribution (which will substitute for their rankings) and stored them in an ascending sorted std::array. I thought to simply represent the draw initially as vector<double> Draw(128). Ideally I would have an algorithm to put each player in the proper position in the draw, but I haven't been able to come up with one yet, so I decided to just type in the positions into an array and select the appropriate array depending on how many players there are in the tournament.

The positions are as follows: 0,127,95,32,64,96,31,63,16,112,79,48,15,111,80,47,41,72,8,119,23,104,55,87,71,39,24,7,56,88,103,120

The first few terms of which in terms as multiples of 32 are: 0*32,4*32-1,3*32-1,1*32,2*32,3*32,1*32-1,2*32-1,0.5*32,3.5*32-1,2.5*32-1,1.5*32,0.5*32-1,3.5*32,2.5*32.

I haven't figured out a pattern from this yet. Is there a known algorithm for this?

Answer 1

Basic algorithm description:

Let's assume you want to seed 4 players in an 8 player tournament.

        [ ][ ][ ][ ][ ][ ][ ][ ]    8 empty positions

To seed the first player is easy, it doesn't really matter where we put him. We put him at the beginning so the algorithm get's easier.

        [1][ ][ ][ ][ ][ ][ ][ ]

If we want to seed the second player we need to split the complete field into two parts. A Player which is in the left part will meet a player from the right only in final. Therefore the second player must be placed into the right part, so that the two best players won't meet before the final match. Again we put the player at the beginning of his part.

      [1][ ][ ][ ]    [2][ ][ ][ ]

Now we split these two parts again, and place the third and fourth player into the new empty parts. Now the third player will encounter the first player in semi-finals.

[1][ ]    [3][ ]        [2][ ]    [4][ ]

Please note that the algorithm places the uneven numbers in the left part and the even numbers in the right part. The empty cells now can be filled with random players. This algorithm is basically the same what @Nico Schertler suggested.

Programming:

My idea would be to define a function which takes the position of a player (e.g. 1,2,3,4 and so on) and the number of free positions (in your example 128) and returns where you should place this player. I wrote the function in Java, but it should be easy to adapt it.

/**
 * @param rank
 *            rank of the player, best player == 1, second best player == 2
 * @param partSize
 *            number of total free positions. Has to be a power of 2 (e.g.
 *            2,4,8,16,32)
 * @return returns the start position of the player, zero based
 */
public static int seedPlayer(int rank, int partSize) {
    // base case, if rank == 1, return position 0
    if (rank <= 1) {
        return 0;
    }

    // if our rank is even we need to put the player into the right part
    // so we add half the part size to his position
    // and make a recursive call with half the rank and half the part size
    if (rank % 2 == 0) {
        return partSize / 2 + seedPlayer(rank / 2, partSize / 2);
    }

    // if the rank is uneven, we put the player in the left part
    // since rank is uneven we need to add + 1 so that it stays uneven
    return seedPlayer(rank / 2 + 1, partSize / 2);
}

Example:

Let's seed our first tournament (8 seeded players, 8 players alltogether)

for (int i = 1; i <= 8; i++) {
    System.out.printf("seeded player %d in position %d%n", i, seedPlayer(i, 8) + 1);
}

This prints:

seeded player 1 in position 1
seeded player 2 in position 5
seeded player 3 in position 3
seeded player 4 in position 7
seeded player 5 in position 2
seeded player 6 in position 6
seeded player 7 in position 4
seeded player 8 in position 8

resulting in this field:

[1][5][3][7][2][6][4][8] Perfect! Like expected!

Further Notice:

I wouldn't seed more than 25% of the players, so that the tournament will change over the years and every not so good player gets a chance to play against different players.

Answer 2

I can think of two approaches:

1. Absurd-Mind's answer and adding a little more information to it.

Not only do we need to separate the top two seeds, to avoid them meeting anywhere before the final round by placing them in two separate halves, we have to make sure that the top seeded player gets to play last seeded player in the first round, the second seeded player gets to play the second last, and so on.

The algorithm proposed by Absurd-Mind actually takes care of that. If I had to change anything, it would only be in the last function seedPlayer. Or I would simply add another step extracting the extremes from either side of his result to place them in another array to get the array positions as asked in the question.

For n=8, 
[1][5][3][7][2][6][4][8] \\previous result

\\extracting the extreme values on either side and placing them in another array:
[1][8] [5][4] [3][6] [7][2]

\\next round (assuming the higher seed wins):
[1][4] [3][2]

\\final round:
[1][2]

Hence, the order obtained initially is correct

2. Observe the pattern

There is no specific formula to obtain the nth term of the series (at least I couldn't find one). But there is a hidden pattern which can be made use of. The pattern emerges when you write the seeding in this particular way:

(Arrowhead indicates the direction of the ascending order)
For n=2,
1 ---> 2

For n=4,
1 ---> 2
4 <--- 3

For n=8,
1 ---> 2
4 <--- 3
5 ---> 6
8 <--- 7

In general,
m ---> m+1
....
....
n <--- n-1

First divide the number of entries (or players) by 2. Let us assume two arrays X and Y (each of size n/2) for convenience. The entries to one side of the arrows are to be stored in array X and the other half in array Y.

1. Enter n (number of players, should be a power of 2)
2. Arrays X[n/2], Y[n/2]
   Integer a=1
3. for (i=1, i<=n/4, i++)
       {
       if(i=1){
         X[i]=a;
         Y[i]=a+1;}
       else if (i%2=0) {  \\if i is even
         X[i]=2i;
         Y[i]=X[i]-1;}
       else {
         X[i]=2i-1;
         Y[i]=X[i]+1; }
       a++;
       }

Resulting arrays (for n=16):
X=[1][4][5][8][9][12][13][16]
Y=[2][3][6][7][10][11][14][15]

Now, we have divided the top two seeds into two separate halves. We have also correspondingly divided the other seeds to avoid unfair match-up in earlier rounds. I would now write another step to extract the extremes in each array and place them in the following order

X= *[1]* [4][5][8][9][12][13] *[16]*
X= *[4]* [5][8][9][12] *[13]* 
and so on...

We obtain,

A=[1][16] [4][13] [5][12] [8][9]

Similarly for the other half,
B=[2][15] [3][14] [6][11] [7][10] 

Continue to extract the winner of the extremes on both sides until you arrive at a winner from both sets A and B, who will play each other in the final.

Hope that helps!

Answer 3

There is a formula for choosing the players in output order.

The math is easier with 0 based player counts, so I will be doing that, transform as needed for output and input.

Start with player seed 0 in position 0.

PC = Player count (filled up with unseeded players then bye's to power of 2)
slot[0] = seeded[0]
for(n = 1; n < PC; n++) {
    seed = slot[n-(1<<ffs(n))]^(PC>>ffs(n))
    slot[n] = seeded[seed];
}

ffs is find first set, also known as a count of trailing 0's. Should return 0 for low bit set.enter code here