我正在尝试构建一个处理比赛括号表的算法。我需要浏览一系列的数字。每个号码都有运动员的名字。数字是随机分配给运动员的，但数字的配对必须始终保持不变有两组奇数和偶数，即A和B。
唯一的问题是，我找不到合适的算法来以的确切方式迭代数字，如下所示：
Group A:
--------
1
17
9
25
------
5
21
13
29
------
3
19
11
27
------
7
23
15
31
Group B:
--------
2
18
10
26
------
6
22
14
30
------
4
20
12
28
------
8
24
16
32
有人能帮忙提供如何获得上述输出的建议或示例吗？
编辑1:
上面的例子是32运动员的括号表！如果您为4,8,16,64或128运动员使用表格，则必须应用相同的逻辑！
编辑2:
让我们以4名运动员的成绩表为例，然后以16名运动员的表现表为例来说明这一点。
4名运动员的名单：
Group A:
--------
1
3
Group B:
--------
2
4
16名运动员的名单：
Group A:
--------
1
9
5
13
------
3
11
7
15
Group B:
--------
2
10
6
14
------
4
12
8
16
编辑3：
最后一部分，我计划有一个数组，其中包含运动员名称及其状态。我所说的状态是指，如果运动员以前是冠军（强），那么他/她获得的状态为1，如果运动员之前的成就未知或最小（弱），那么状态为0。这样做，我们就可以把最强壮的运动员分成不同的小组，确保他们不会在第一场比赛中相互对抗，而是在半决赛或决赛前相遇。
PHP数组示例：
$participants = array(
array("John", 0),
array("Gagan", 0),
array("Mike Tyson", 1),
array("Gair", 0),
array("Gale", 0),
array("Roy Johnes", 1),
array("Galip", 0),
array("Gallagher", 0),
array("Garett", 0),
array("Nikolai Valuev", 1),
array("Garner", 0),
array("Gary", 0),
array("Gelar", 0),
array("Gershom", 0),
array("Gilby", 0),
array("Gilford", 0)
);
从这个例子中，我们可以看到，那些状态为1的人必须属于不同的组，即A和B。但我们只有两组数字奇数和偶数，在这个例子中，有3名强壮的运动员。因此，他们中的两人将属于同一组。最终的结果必须是，同组的两名强壮运动员，不能在第一场比赛中相遇（这意味着他们不会在同一对数字上，也不会尽可能远离对方，所以他们也不会在第二场比赛中见面）。
然后，随机地，我计划重新排列阵列，并将运动员发送到括号表中-每次，使用不同的数字，每次<strong]，那些有旗帜>1的运动员会被分配到不同的组和/或从未在第一场比赛中相遇和每次，运动员的名字被分配到同一对数字
考虑到参与者的数量总是2的幂，这段代码应该会给出您期望的顺序。
function getOrder($numberOfParticipants) {
$order = array(1, 2);
for($i = 2; $i < $numberOfParticipants; $i <<= 1) {
$nextOrder = array();
foreach($order as $number) {
$nextOrder[] = $number;
$nextOrder[] = $number + $i;
}
$order = $nextOrder;
}
return $order; // which is for instance [1, 17, 9, 25, and so on...] with 32 as argument
}
关于它的工作方式，让我们看看当参与者人数翻倍时会发生什么。
Participants | Order
2 | 1 2
4 | 1 3=1+2 2 4=2+2
8 | 1 5=1+4 3 7=3+4 2 6=2+4 4 8=4+4
... |
N | 1 X Y Z ...
2N | 1 1+N X X+N Y Y+N Z Z+N ...
我使用的算法是完全相同的逻辑。我从一个只包含[1, 2]的数组开始，而$i实际上就是这个数组的大小。然后我计算下一行，直到到达参与者人数合适的那一行。
附带说明：$i <<= 1与$i *= 2的作用相同。您可以阅读有关位运算符的文档以获得进一步的解释。
关于strong运动员，因为你想保持尽可能多的随机性，这里有一个解决方案（可能不是最优的，但这是我最初的想法）：
- 制作两个阵列，一个带有强，另一个带有弱
- 如果没有strong或只有一个，只需洗牌整个数组并转到8
- 如果strong比weak多（不知道在您的情况下是否会发生这种情况，但最好是安全的，而不是抱歉），请打乱strong，并将最后一个放在Weak
- 否则，用
null元素填充strongs，使数组大小为2的幂，然后对其进行混洗- 洗牌
- 根据strongs数组中的元素准备尽可能多的组，并在每组中放入一个strong（如果您有
null元素，则不放入），并根据需要完成尽可能多弱点- 打乱每组
- 返回参与者，按与上一个函数结果数组相同的方式排序
- 否则，用
以及相应的代码：
function splitStrongsAndWeaks($participants) {
$strongs = array();
$weaks = array();
foreach($participants as $participant) {
if($participant != null && $participant[1] == 1)
$strongs[] = $participant;
else
$weaks[] = $participant;
}
return array($strongs, $weaks);
}
function insertNullValues($elements, $totalNeeded)
{
$strongsNumber = count($elements);
if($strongsNumber == $totalNeeded)
return $elements;
if($strongsNumber == 1)
{
if(mt_rand(0, 1))
array_unshift($elements, null);
else
$elements[] = null;
return $elements;
}
if($strongsNumber & 1)
$half = ($strongsNumber >> 1) + mt_rand(0, 1);
else
$half = $strongsNumber >> 1;
return array_merge(insertNullValues(array_splice($elements, 0, $half), $totalNeeded >> 1), insertNullValues($elements, $totalNeeded >> 1));
}
function shuffleParticipants($participants, $totalNeeded) {
list($strongs, $weaks) = splitStrongsAndWeaks($participants);
// If there are only weaks or a single strong, just shuffle them
if(count($strongs) < 2) {
shuffle($participants);
$participants = insertNullValues($participants, $totalNeeded);
}
else {
shuffle($strongs);
// If there are more strongs, we need to put some with the weaks
if(count($strongs) > $totalNeeded / 2) {
list($strongs, $strongsToWeaks) = array_chunk($strongs, $totalNeeded / 2);
$weaks = array_merge($weaks, $strongToWeaks);
$neededGroups = $totalNeeded / 2;
}
// Else we need to make sure the number of groups will be a power of 2
else {
$neededGroups = 1 << ceil(log(count($strongs), 2));
if(count($strongs) < $neededGroups)
$strongs = insertNullValues($strongs, $neededGroups);
}
shuffle($weaks);
// Computing needed non null values in each group
$neededByGroup = $totalNeeded / $neededGroups;
$neededNonNull = insertNullValues(array_fill(0, count($participants), 1), $totalNeeded);
$neededNonNull = array_chunk($neededNonNull, $neededByGroup);
$neededNonNull = array_map('array_sum', $neededNonNull);
// Creating groups, putting 0 or 1 strong in each
$participants = array();
foreach($strongs as $strong) {
$group = array();
if($strong != null)
$group[] = $strong;
$nonNull = array_shift($neededNonNull);
while(count($group) < $nonNull)
$group[] = array_shift($weaks);
while(count($group) < $neededByGroup)
$group[] = null;
// Shuffling again each group so you can get for instance 1 -> weak, 17 -> strong
shuffle($group);
$participants[] = $group;
}
// Flattening to get a 1-dimension array
$participants = call_user_func_array('array_merge', $participants);
}
// Returned array contains participants ordered the same way as getOrder()
// (eg. with 32 participants, first will have number 1, second number 17 and so on...)
return $participants;
}
如果您希望得到的数组将括号中的数字作为索引，您可以简单地执行以下操作：
$order = getOrder(count($participants));
$participants = array_combine($order, shuffleParticipants($participants, count($order)));
好吧，我终于把Tcl代码转换成了PHP！我也改变了一些东西：
<?php
// Function generating order participants will be placed in array
function getBracket($L) {
// List will hold insert sequence
$list = array();
// Bracket will hold final order of participants
$bracket = array();
// The algorithm to generate the insert sequence
for ($n = 1; $n <= $L; $n += 1) {
// If 'perfect' number, just put it (Perfect no.s: 2, 4, 8, 16, 32, etc)
if (substr(log($n)/log(2), -2) == ".0") {
$list[] = $n;
// If odd number, stuff...
} elseif ($n % 2 == 1) {
$list[] = $list[($n-1)/2];
// Else even number, stuff...
} else {
$list[] = $list[$n/2-1]+$n/2;
}
}
// Insert participant order as per insert sequence
for ($i = 1; $i <= sizeof($list); $i += 1) {
$id = $i-1;
array_splice($bracket, $list[$id], 0, $i);
}
return $bracket;
}
// Find number of participants over 'perfect' number if any
function cleanList($L) {
for ($d = 1; $L > $d; $d += 1) {
$sq = $L-pow(2,$d);
if($sq == 0) {break;}
if($sq < 0) {
$d = pow(2,$d-1);
$diff = $L-$d;
break;
}
}
return $diff;
}
$participants = array(
array(0, "John", 2),
array(1, "Gagan", 1),
array(2, "Mike Tyson", 1),
array(3, "Gair", 1),
array(4, "Gale", 0),
array(5, "Roy Johnes", 0),
array(6, "Galip", 0),
array(7, "Gallagher", 0),
array(8, "Garett", 0),
array(9, "Nikolai Valuev", 0),
array(10, "Garner", 1),
array(11, "Gary", 0),
array(12, "Gelar", 0),
array(13, "Gershom", 1),
array(14, "Gilby", 0),
array(15, "Gilford", 1),
array(16, "Arianna", 0)
);
// Extract strength of participant
foreach ($participants as $array) {
$finorder[] = $array[2];
}
// Sort by strength, strongest first
array_multisort($finorder,SORT_DESC,$participants);
$order = array();
$outside = array();
// Remove participants above 'perfect' number
$remove = cleanList(sizeof($participants));
for ($r = 1; $r <= $remove; $r += 1) {
$removed = array_shift($participants);
$outside[] = $removed;
}
// Get corresponding bracket
$res = getBracket(sizeof($participants));
foreach ($res as $n) {
$order[] = $n;
}
// Align bracket results with participant list
array_multisort($order, $participants);
$participants = array_combine($res, $participants);
echo "The final arrangement of participants'n";
print_r($participants);
print_r($outside);
?>
Codepad演示
为了获得元素插入顺序的逻辑，我使用了这个模式。
此外，由于我对PHP不太熟悉，可能有一些方法可以缩短一些内容，但哦，好吧，只要它能工作^^
编辑：修复了第一个参与者排序的问题，并添加了新的票号。有关没有旧票号的结果，请参阅此处。
EDIT2：设法将键移动到数组中；请看这里。
编辑3：我认为"额外"的参与者应该超出范围。如果你想在括号中使用null，你可以使用这个。
第4版：不知怎么的，代码板上的PHP版本破坏了一些东西。。。在下面修复它并删除初始索引…：
<?php
// Function generating order participants will be placed in array
function getBracket($L) {
// List will hold insert sequence
$list = array();
// Bracket will hold final order of participants
$bracket = array();
// The algorithm to generate the insert sequence
for ($n = 1; $n <= $L; $n += 1) {
// If 'perfect' number, just put it (Perfect no.s: 2, 4, 8, 16, 32, etc)
if (int(log($n)/log(2)) || $n == 1) {
$list[] = $n;
// If odd number, stuff...
} elseif ($n % 2 == 1) {
$list[] = $list[($n-1)/2];
// Else even number, stuff...
} else {
$list[] = $list[$n/2-1]+$n/2;
}
}
// Insert participant order as per insert sequence
for ($i = 1; $i <= sizeof($list); $i += 1) {
$id = $list[$i-1]-1;
array_splice($bracket, $id, 0, $i);
}
return $bracket;
}
// Find number of participants over 'perfect' number if any
function cleanList($L) {
for ($d = 1; $L > $d; $d += 1) {
$diff = $L-pow(2,$d);
if($diff == 0) {break;}
if($diff < 0) {
$diff = pow(2,$d)-$L;
break;
}
}
return $diff;
}
$participants = array(
array("John", 2),
array("Gagan", 1),
array("Mike Tyson", 1),
array("Gair", 1),
array("Gale", 0),
array("Roy Johnes", 0),
array("Galip", 0),
array("Gallagher", 0),
array("Garett", 0),
array("Nikolai Valuev", 0),
array("Garner", 1),
);
// Extract strength of participant
foreach ($participants as $array) {
$finorder[] = $array[2];
}
// Sort by strength, strongest first
array_multisort($finorder,SORT_DESC,$participants);
$order = array();
// Add participants until 'perfect' number
$add = cleanList(sizeof($participants));
for ($r = 1; $r <= $add; $r += 1) {
$participants[] = null;
}
// Get corresponding bracket
$res = getBracket(sizeof($participants));
// Align bracket results with participant list
foreach ($res as $n) {
$order[] = $n;
}
array_multisort($order, $participants);
$participants = array_combine($res, $participants);
echo "The final arrangement of participants'n";
print_r($participants);
?>
ideone
viper-7
这个粗略的代码可能就是你想要的：
<?php
class Pair
{
public $a;
public $b;
function __construct($a, $b) {
if(($a & 1) != ($b & 1))
throw new Exception('Invalid Pair');
$this->a = $a;
$this->b = $b;
}
}
class Competition
{
public $odd_group = array();
public $even_group = array();
function __construct($order) {
$n = 1 << $order;
$odd = array();
$even = array();
for($i = 0; $i < $n; $i += 4) {
$odd[] = $i + 1;
$odd[] = $i + 3;
$even[] = $i + 2;
$even[] = $i + 4;
}
shuffle($odd);
shuffle($even);
for($i = 0; $i < count($odd); $i += 2) {
$this->odd_group[] = new Pair($odd[$i], $odd[$i+1]);
$this->even_group[] = new Pair($even[$i], $even[$i+1]);
}
echo "Odd'n";
for($i = 0; $i < count($this->odd_group); ++$i) {
$pair = $this->odd_group[$i];
echo "{$pair->a} vs. {$pair->b}'n";
}
echo "Even'n";
for($i = 0; $i < count($this->even_group); ++$i) {
$pair = $this->even_group[$i];
echo "{$pair->a} vs. {$pair->b}'n";
}
}
}
new Competition(5);
?>