我正在尝试创建一些逻辑来生成 double-elimination tournament bracket 中的事件时间表.

这是一个 8 队分组的示例:

rd1 quarter    semi    finals
A───┐
  0 ├───────A┐
B───┘        │
           4 ├────────A┐
C───┐        │         │
  1 ├───────C┘         │
D───┘                  │
                    10 ├──────A┐
E───┐                  │       │
  2 ├───────E┐         │       │
F───┘        │         │       │
           5 ├────────E┘       │
G───┐        │              13 ├───= Champ
  3 ├───────G┘                 │
H───┘                          │
                    E────┐     │
         C───┐           │     │
    B───┐  8 ├────C┐  12 ├────E┘
      6 ├B───┘     │     │
    D───┘       11 ├C────┘
         G───┐     │
    F───┐  9 ├────G┘
      7 ├F───┘
    H───┘

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

输家组由赢家组的输家组成，其中索引 6 是索引 0 的输家与索引 1 的输家，索引 8 是索引 4 的输家与索引 6 的赢家。

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

出现了一个明显的模式，但当我尝试适应不同数量的竞争对手时，我的逻辑变得困惑和困惑。为简单起见，我将括号固定为团队数量的 2 次幂。我能够编写所有内容来为 8 支队伍创建匹配数组，但我什至对自己的代码都失去了理解，因为它似乎不可扩展。

// 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 );

// quarter finals
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 )
    ) );
}

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

$round_matchups = array( );
for( $i = 0; $i < count( $competitors ) / 2 / 2; $i++ )
{
    array_push( $round_matchups, array(
        array( 'from_event_index' => $i + count( $competitors ), 'from_event_rank' => 1 ),
        array( 'from_event_index' => ++$i + count( $competitors ), 'from_event_rank' => 1 )
    ) );
}
$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 ) + count( $competitors ) / 2 - 2, 'from_event_rank' => 2 ),
        array( 'from_event_index' => $i + count( $competitors ) + count( $competitors ) / 2 - 1, 'from_event_rank' => 1 )
    ) );
}

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

上面代码的输出:

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

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

最佳答案

好吧，我一直在努力研究我现有的逻辑，并且能够生成 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 个团队的时间表，看起来是正确的。有时，坚持会有返回。

关于php - 双败赛程，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21536226/