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

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?

Solution

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.