双败淘汰赛赛程

Question

我正在尝试创建一些逻辑来生成双败淘汰赛分组中的赛事时间表中的赛事时间表。

\n\n

以下是 8 队分组示例：

\n\n

rd1 quarter    semi    finals\nA\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90\n  0 \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80A\xe2\x94\x90\nB\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98        \xe2\x94\x82\n           4 \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80A\xe2\x94\x90\nC\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90        \xe2\x94\x82         \xe2\x94\x82\n  1 \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80C\xe2\x94\x98         \xe2\x94\x82\nD\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98                  \xe2\x94\x82\n                    10 \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80A\xe2\x94\x90\nE\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90                  \xe2\x94\x82       \xe2\x94\x82\n  2 \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80E\xe2\x94\x90         \xe2\x94\x82       \xe2\x94\x82\nF\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98        \xe2\x94\x82         \xe2\x94\x82       \xe2\x94\x82\n           5 \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80E\xe2\x94\x98       \xe2\x94\x82\nG\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90        \xe2\x94\x82              13 \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80= Champ\n  3 \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80G\xe2\x94\x98                 \xe2\x94\x82\nH\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98                          \xe2\x94\x82\n                    E\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90     \xe2\x94\x82\n         C\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90           \xe2\x94\x82     \xe2\x94\x82\n    B\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90  8 \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80C\xe2\x94\x90  12 \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80E\xe2\x94\x98\n      6 \xe2\x94\x9cB\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98     \xe2\x94\x82     \xe2\x94\x82\n    D\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98       11 \xe2\x94\x9cC\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98\n         G\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90     \xe2\x94\x82\n    F\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x90  9 \xe2\x94\x9c\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80G\xe2\x94\x98\n      7 \xe2\x94\x9cF\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98\n    H\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\x98\n

\n\n

这些数字表示匹配数组中的索引，这是所需的输出。例如，索引 0 将代表第 1 队与第 8 队（使用种子系统），索引 4 将代表索引 0 的获胜者与索引 1 的获胜者。

\n\n

败者组由胜者组的失败者填充，其中索引 6 是索引 0 的失败者与索引 1 的失败者，索引 8 是索引 4 的失败者与索引 4 的获胜者索引 6.

\n\n

在可视化示例中，您可以看到用字母标记的团队，并清楚地显示获胜团队每次都位于顶部分支，失败团队位于底部分支的清晰示例。索引 0 代表 A 队对 B 队，索引 4 代表索引 0 的获胜者 (A) 与索引 1 的获胜者 (C)。指数 6 是指数 0 (B) 的输家与指数 1 (D) 的输家，指数 8 是指数 4 (C) 的输家与指数 6 (B) 的赢家

\n\n

出现了一种明显的模式，但当我试图适应不同数量的竞争对手时，我的逻辑变得混乱和混乱。为了简单起见，我将括号固定为仅 2 的幂个团队数。我能够编写所有内容来为 8 支球队创建一组比赛，但我什至无法理解自己的代码，因为它似乎不可扩展。

\n\n

// round one\nfor( $i = 0; $i < log( count( $competitors ), 2 ); $i++ )\n{\n    $seeded = array( );\n    foreach( $competitors as $competitor )\n    {\n        $splice = pow( 2, $i );\n\n        $seeded = array_merge( $seeded, array_splice( $competitors, 0, $splice ) );\n        $seeded = array_merge( $seeded, array_splice( $competitors, -$splice ) );\n    }\n    $competitors = $seeded;\n}\n\n$events = array_chunk( $seeded, 2 );\n\n// quarter finals\nfor( $i = 0; $i < count( $competitors ) / 2; $i++ )\n{\n    array_push( $events, array(\n        array( \'from_event_index\' => $i, \'from_event_rank\' => 1 ), // rank 1 = winner\n        array( \'from_event_index\' => ++$i, \'from_event_rank\' => 1 )\n    ) );\n}\n\n$round_matchups = array( );\nfor( $i = 0; $i < count( $competitors ) / 2; $i++ )\n{\n    array_push( $round_matchups, array(\n        array( \'from_event_index\' => $i, \'from_event_rank\' => 2 ), // rank 2 = loser\n        array( \'from_event_index\' => ++$i, \'from_event_rank\' => 2 )\n    ) );\n}\n$events = array_merge( $events, $round_matchups );\n\nfor( $i = 0; $i < count( $round_matchups ); $i++ )\n{\n    array_push( $events, array(\n        array( \'from_event_index\' => $i + count( $competitors ) / 2, \'from_event_rank\' => 2 ),\n        array( \'from_event_index\' => $i + count( $competitors ) / 2 + count( $competitors ) / 2 / 2, \'from_event_rank\' => 1 )\n    ) );\n}\n\n// semi finals\nfor( $i = 0; $i < count( $competitors ) / 2 / 2; $i++ )\n{\n    array_push( $events, array(\n        array( \'from_event_index\' => $i + count( $competitors ) / 2, \'from_event_rank\' => 1 ),\n        array( \'from_event_index\' => ++$i + count( $competitors ) / 2, \'from_event_rank\' => 1 )\n    ) );\n}\n\n$round_matchups = array( );\nfor( $i = 0; $i < count( $competitors ) / 2 / 2; $i++ )\n{\n    array_push( $round_matchups, array(\n        array( \'from_event_index\' => $i + count( $competitors ), \'from_event_rank\' => 1 ),\n        array( \'from_event_index\' => ++$i + count( $competitors ), \'from_event_rank\' => 1 )\n    ) );\n}\n$events = array_merge( $events, $round_matchups );\n\nfor( $i = 0; $i < count( $round_matchups ); $i++ )\n{\n    array_push( $events, array(\n        array( \'from_event_index\' => $i + count( $competitors ) + count( $competitors ) / 2 - 2, \'from_event_rank\' => 2 ),\n        array( \'from_event_index\' => $i + count( $competitors ) + count( $competitors ) / 2 - 1, \'from_event_rank\' => 1 )\n    ) );\n}\n\n// finals\nfor( $i = 0; $i < count( $competitors ) / 2 / 2 / 2; $i++ )\n{\n    array_push( $events, array(\n        array( \'from_event_index\' => $i + count( $competitors ) / 2 * 3 - 2, \'from_event_rank\' => 1 ),\n        array( \'from_event_index\' => ++$i + count( $competitors ) / 2 * 3 - 1, \'from_event_rank\' => 1 )\n    ) );\n}\n

\n\n

上面代码的输出：

\n\n

$events = array(14) {\n  [0]=>\n  array(2) {\n    [0]=>\n    array(4) {\n      ["team"]=>int(1)\n    }\n    [1]=>\n    array(4) {\n      ["team"]=>int(8)\n    }\n  }\n  [1]=>\n  array(2) {\n    [0]=>\n    array(4) {\n      ["team"]=>int(4)\n    }\n    [1]=>\n    array(4) {\n      ["team"]=>int(5)\n    }\n  }\n  [2]=>\n  array(2) {\n    [0]=>\n    array(4) {\n      ["team"]=>int(2)\n    }\n    [1]=>\n    array(4) {\n      ["team"]=>int(7)\n    }\n  }\n  [3]=>\n  array(2) {\n    [0]=>\n    array(4) {\n      ["team"]=>int(3)\n    }\n    [1]=>\n    array(4) {\n      ["team"]=>int(6)\n    }\n  }\n  [4]=>\n  array(2) {\n    [0]=>\n    array(2) {\n      ["from_event_index"]=>int(0)\n      ["from_event_rank"]=>int(1)\n    }\n    [1]=>\n    array(2) {\n      ["from_event_index"]=>int(1)\n      ["from_event_rank"]=>int(1)\n    }\n  }\n  [5]=>\n  array(2) {\n    [0]=>\n    array(2) {\n      ["from_event_index"]=>int(2)\n      ["from_event_rank"]=>int(1)\n    }\n    [1]=>\n    array(2) {\n      ["from_event_index"]=>int(3)\n      ["from_event_rank"]=>int(1)\n    }\n  }\n  [6]=>\n  array(2) {\n    [0]=>\n    array(2) {\n      ["from_event_index"]=>int(0)\n      ["from_event_rank"]=>int(2)\n    }\n    [1]=>\n    array(2) {\n      ["from_event_index"]=>int(1)\n      ["from_event_rank"]=>int(2)\n    }\n  }\n  [7]=>\n  array(2) {\n    [0]=>\n    array(2) {\n      ["from_event_index"]=>int(2)\n      ["from_event_rank"]=>int(2)\n    }\n    [1]=>\n    array(2) {\n      ["from_event_index"]=>int(3)\n      ["from_event_rank"]=>int(2)\n    }\n  }\n  [8]=>\n  array(2) {\n    [0]=>\n    array(2) {\n      ["from_event_index"]=>int(4)\n      ["from_event_rank"]=>int(2)\n    }\n    [1]=>\n    array(2) {\n      ["from_event_index"]=>int(6)\n      ["from_event_rank"]=>int(1)\n    }\n  }\n  [9]=>\n  array(2) {\n    [0]=>\n    array(2) {\n      ["from_event_index"]=>int(5)\n      ["from_event_rank"]=>int(2)\n    }\n    [1]=>\n    array(2) {\n      ["from_event_index"]=>int(7)\n      ["from_event_rank"]=>int(1)\n    }\n  }\n  [10]=>\n  array(2) {\n    [0]=>\n    array(2) {\n      ["from_event_index"]=>int(4)\n      ["from_event_rank"]=>int(1)\n    }\n    [1]=>\n    array(2) {\n      ["from_event_index"]=>int(5)\n      ["from_event_rank"]=>int(1)\n    }\n  }\n  [11]=>\n  array(2) {\n    [0]=>\n    array(2) {\n      ["from_event_index"]=>int(8)\n      ["from_event_rank"]=>int(1)\n    }\n    [1]=>\n    array(2) {\n      ["from_event_index"]=>int(9)\n      ["from_event_rank"]=>int(1)\n    }\n  }\n  [12]=>\n  array(2) {\n    [0]=>\n    array(2) {\n      ["from_event_index"]=>int(10)\n      ["from_event_rank"]=>int(2)\n    }\n    [1]=>\n    array(2) {\n      ["from_event_index"]=>int(11)\n      ["from_event_rank"]=>int(1)\n    }\n  }\n  [13]=>\n  array(2) {\n    [0]=>\n    array(2) {\n      ["from_event_index"]=>int(10)\n      ["from_event_rank"]=>int(1)\n    }\n    [1]=>\n    array(2) {\n      ["from_event_index"]=>int(12)\n      ["from_event_rank"]=>int(1)\n    }\n  }\n}\n

\n\n

关于如何修改它以适用于 4 队、16 队或 2^n 队的分组，有什么想法吗？我觉得“半决赛”标题下的逻辑应该重复0次以上，但每次我尝试根据总轮数循环它时，它只是重复与上一轮相同的比赛。

\n

Answer 1

嗯，我一直在探索现有的逻辑，并能够生成 4、8、16 和 32 队双败淘汰赛的时间表。逻辑不一定简洁，但至少让我明白发生了什么。将来，我希望对其进行一些修改和清理，但现在只能这样做了。

$rounds = log( count( $competitors ), 2 ) + 1;

// round one
for( $i = 0; $i < log( count( $competitors ), 2 ); $i++ )
{
    $seeded = array( );
    foreach( $competitors as $competitor )
    {
        $splice = pow( 2, $i );

        $seeded = array_merge( $seeded, array_splice( $competitors, 0, $splice ) );
        $seeded = array_merge( $seeded, array_splice( $competitors, -$splice ) );
    }
    $competitors = $seeded;
}

$events = array_chunk( $seeded, 2 );

if( $rounds > 2 )
{
    $round_index = count( $events );

    // second round
    for( $i = 0; $i < count( $competitors ) / 2; $i++ )
    {
        array_push( $events, array(
            array( 'from_event_index' => $i, 'from_event_rank' => 1 ), // rank 1 = winner
            array( 'from_event_index' => ++$i, 'from_event_rank' => 1 )
        ) );
    }

    $round_matchups = array( );
    for( $i = 0; $i < count( $competitors ) / 2; $i++ )
    {
        array_push( $round_matchups, array(
            array( 'from_event_index' => $i, 'from_event_rank' => 2 ), // rank 2 = loser
            array( 'from_event_index' => ++$i, 'from_event_rank' => 2 )
        ) );
    }
    $events = array_merge( $events, $round_matchups );

    for( $i = 0; $i < count( $round_matchups ); $i++ )
    {
        array_push( $events, array(
            array( 'from_event_index' => $i + count( $competitors ) / 2, 'from_event_rank' => 2 ),
            array( 'from_event_index' => $i + count( $competitors ) / 2 + count( $competitors ) / 2 / 2, 'from_event_rank' => 1 )
        ) );
    }
}

if( $rounds > 3 )
{
    // subsequent rounds
    for( $i = 0; $i < $rounds - 3; $i++ )
    {
        $round_events = pow( 2, $rounds - 3 - $i );
        $total_events = count( $events );

        for( $j = 0; $j < $round_events; $j++ )
        {
            array_push( $events, array(
                array( 'from_event_index' => $j + $round_index, 'from_event_rank' => 1 ),
                array( 'from_event_index' => ++$j + $round_index, 'from_event_rank' => 1 )
            ) );
        }

        for( $j = 0; $j < $round_events; $j++ )
        {
            array_push( $events, array(
                array( 'from_event_index' => $j + $round_index + $round_events * 2, 'from_event_rank' => 1 ),
                array( 'from_event_index' => ++$j + $round_index + $round_events * 2, 'from_event_rank' => 1 )
            ) );
        }

        for( $j = 0; $j < $round_events / 2; $j++ )
        {
            array_push( $events, array(
                array( 'from_event_index' => $j + $total_events, 'from_event_rank' => 2 ),
                array( 'from_event_index' => $j + $total_events + $round_events / 2, 'from_event_rank' => 1 )
            ) );
        }

        $round_index = $total_events;
    }

}

if( $rounds > 1 )
{
    // finals
    array_push( $events, array(
        array( 'from_event_index' => count( $events ) - 3, 'from_event_rank' => 1 ),
        array( 'from_event_index' => count( $events ) - 1, 'from_event_rank' => 1 )
     ) );
}

我已经验证了最多 32 个团队的结果（仅限 2 的幂），并且能够生成包含 64 个团队的时间表，该时间表似乎是正确的。有时，坚持会有回报。