在 128 人锦标赛中安排 32 名种子选手的算法

Question

我正在尝试创建一个网球锦标赛模拟器，其中比赛的结果是随机的(某种程度上)。大满贯赛事共有 128 名选手，其中 32 名是种子选手。目前我正在尝试将种子放在抽签中的适当位置。我根据正态分布(这将代替他们的排名)生成球员的实力，并将它们存储在升序排序的 std::array 中。我想简单地将平局最初表示为 vector<double> Draw(128) .理想情况下，我会有一个算法将每个玩家放在平局中的正确位置，但我还没有想出一个，所以我决定只将位置输入一个数组并根据需要选择合适的数组关于锦标赛中有多少玩家。

位置如下: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

以32的倍数表示的前几项是: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.

我还没有从中找出一个模式。这有已知的算法吗？

Answer 1

基本算法说明:

假设您想在 8 人锦标赛中安排 4 名选手。

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

让第一个球员成为种子很容易，我们把他放在哪里并不重要。我们把他放在开头，这样算法就更容易了。

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

如果我们想为第二个玩家播种，我们需要将整个 field 分成两部分。位于左侧的玩家只会在决赛中遇到来自右侧的玩家。因此，第二名选手必须放在正确的位置，这样两个最好的选手才不会在决赛前相遇。我们再次将播放器放在他的部分的开头。

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

现在我们再次拆分这两个部分，并将第三个和第四个玩家放入新的空白部分。现在第三名选手将在半决赛中遇到第一名选手。

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

请注意算法将奇数放在左边，偶数放在右边。现在可以用随机玩家填充空单元格。该算法与@Nico Schertler 建议的算法基本相同。

编程:

我的想法是定义一个函数，该函数获取玩家的位置(例如 1、2、3、4 等)和空闲位置的数量(在您的示例中为 128)并返回您应该放置它的位置播放器。我用 Java 编写了这个函数，但应该很容易适应它。

/**
 * @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);
}

示例:

让我们开始我们的第一场比赛(8 名种子选手，总共 8 名选手)

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

这打印:

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

导致这个领域:

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

进一步通知:

我不会选择超过 25% 的选手，这样锦标赛会随着时间的推移而变化，每个不太好的选手都有机会与不同的选手比赛。