php - 生成配对组，没有重复项，php和mysql

我找了一年的时间想弄清楚这个问题。我试图建立一个支架运行系统，运行保龄球支架。
我有一个ID列和BowlerID列的表，称之为bowling_bracket_entries。ID是唯一的，但同一BowlerID可以有多个条目，范围从8到1。我想做的是从BowlerID行中配对，但不要重复同一对，然后从这些配对中，将它们放在4对的组中，在4对的组中没有BowlerID重复。
bowling.bracket_entries表的结构
身份证| BowlerID

我试着随机选择两个BowlerID，并将它们与分隔符（即22~100）放在一起，然后插入到配对表中，然后拉下一个配对（即36~92），创建一个与该配对相反的变量（即92~36），并检查配对表中是否有匹配的值，如果没有找到，则插入，从Entries表中删除这些bowlerid的ID，并重复这些ID，直到其值用完为止。问题是有时我会得到一个BowlerID配对本身。偶尔，我会得到一个完整的列表，没有BowlerID与他们配对。

SELECT bracket_entries.ID, bracket_entries.BowlerID FROM bracket_entries ORDER BY rand() LIMIT 2

然后把它们组合在一起，形成一对（即36~68）

$i = 0;
    while($pairing=$rsNewPair->fetch_assoc()) {
        //Build Pairing List
        $thisPairing .= $pairing['BowlerID'];
        $IDS .= $pairing['ID'];
        $i++;
            if($i < 2){
                $thisPairing .= "~";
                $IDS .= "~";
            }
        }


$flipFlop = explode('~', $thisPairing);
    $reversePairing = $flipFlop[1].'~'.$flipFlop[0];
    if($flipFlop[0] == $flipFlop[1]){
        header("Refresh:0");
    }

和已经存在的东西相比。

SELECT bracket_pairings.Pairing FROM bracket_pairings WHERE bracket_pairings.Pairing = '".$thisPairing."' OR bracket_pairings.Pairing = '".$reversePairing."'"

如果找不到任何东西，则将配对插入配对表，然后转到下一个2
保龄球托架配对台结构

    1 203~218
2 193~218
3 217~129
4 201~60
5 60~141
6 141~165
7 197~202
8 230~203
9 220~167
10 60~62
11 151~140
12 151~230
13 193~205
14 60~140
15 217~223
16 203~142
17 60~205
18 197~151
19 205~201
20 218~62
21 56~223
22 217~167
23 56~202
24 217~75
25 224~223
26 160~203
27 151~60
28 131~145
29 140~205
30 202~75
31 62~160
32 142~181
33 224~181
34 145~223
35 165~56
36 218~202

SELECT
PairingID, SUBSTRING_INDEX(Pairing, '~', 1) AS entry1,
SUBSTRING_INDEX(SUBSTRING_INDEX(Pairing, '~', 2), '~', -1) AS entry2

从托架配对
然后使用while循环在方括号中显示配对，并将4对的每个条目推入数组中，直到其满为止，然后进行比较，以确保没有任何用户重复。

while(($pairings=$rsEntries->fetch_assoc())&&($loop < 5)){
    $thisBowlerID1 = $pairings['entry1'];
    $thisBowlerID2 = $pairings['entry2'];

    if((!in_array($thisBowlerID1, $thisBracket)) || (!in_array($thisBowlerID2, $thisBracket))){
    while($players=$rsPlayers->fetch_assoc()){
            if($players['BowlerID'] == $thisBowlerID1){
                echo $players['BowlerID'].'<br>';
                //echo $players['Name'].'('.$players['CurrentAvg'].')<br>';
            }
    } mysqli_data_seek($rsPlayers, 0);
    array_push($thisBracket, $thisBowlerID1);

    while($players=$rsPlayers->fetch_assoc()){
        if($players['BowlerID'] == $thisBowlerID2){
            echo $players['BowlerID'].'<br><br>';
            //echo $players['Name'].'('.$players['CurrentAvg'].')<br><br>';
    }
    } mysqli_data_seek($rsPlayers, 0);
    array_push($thisBracket, $thisBowlerID2);

    $removeSQL="DELETE FROM bracket_pairings WHERE bracket_pairings.PairingID = ".$pairings['PairingID'];
    $removePairing = $connAdmin->query($removeSQL);
    $loop++;
    }
    $thisBracket = array();
}
}

我有72个条目，当我试着把它们分成4组（8个条目）时，它似乎从来没有填满9个括号，只有大约7.5个，然后在表中留下一个没有放置的随机配对组合，但我仍然有空缺。
结果

如你所见，结果留下8个空缺。
以下是未包含的剩余部分：

5   197~218
10  60~223
15  181~62
20  203~60
25  160~217
30  151~151
35  145~224

不知道为什么五分之一的人都跳过。我认为我走在了正确的轨道上，但任何帮助或想法，以找出如何解决问题，我有将是伟大的。

最佳答案

好的，首先：不要把配对保存为“203~60”这样的字符串。当必须一直合并/拆分值时，使用数据库会变得更加困难。您的桌子应该在3NF中。
第二：在构建配对时，不要将配对保存在数据库中。将它们保存在php的内存中，以避免任何不必要的数据库调用，只是为了查看是否已经添加了配对，这样做要快得多。
也就是说，有一些算法你可以查找你的问题。您应该检查以下链接：
Is there a known algorithm for scheduling tournament matchups?他们在softwareengineering.stackexchange.com上的相关问题（这可能是一个更好的提问的地方，但要检查重复的问题）
https://en.wikipedia.org/wiki/Matching_%28graph_theory%29
https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm
https://en.wikipedia.org/wiki/Backtracking
我可以想出一些算法，但在某些情况下失败了。算法的工作原理如下：
您可以使用https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm上的算法为9个团队（每个团队有8个成员）创建计划。假设他们被称为“a”到“i”。配对将如下所示：

abcd  aibc  ahib  aghi afgh
hgfe  gfed  fedc  edcb dcbi

aefg  adef  acde  bcfg
cbih  bihg  ihgf  dehi

通过将“a”团队固定在适当的位置，并围绕桌子/配对轮换其余的团队，可以获得此种子。不过，你必须跳过一个队，因为你有9个队4*2可能的种子。在第九组中，“a”队不见了，剩下的种子是“b”到“i”。
当我们有这9个团队，每个团队有8名成员时，他们的代表如下：

aaaaaaaa
bbbbbbbb
cccccccc
dddddddd
eeeeeeee
ffffffff
gggggggg
hhhhhhhh
iiiiiiii

当你有9个以上的团队时，你应该试着把他们组合在一起，就像他们属于一个8号的伪团队一样。可以这样看：

aaaaaabb
ccccddde
fffffggg
hhiijjjj
kkkkklll
mmmmnnnn
ooopppqq
rrrrrsss
ttuuvvww

由于这些团队是在“同一个”伪团队上，所以它们不匹配，算法仍然有效。
但是，如果不能将团队放入8大小的伪团队中，则算法将失败。假设你有2个8人小组和8个7号小组。这个
伪团队如下所示：

aaaaaaaa
bbbbbbbb
cccccccj
dddddddj
eeeeeeej
fffffffj
gggggggj
hhhhhhhj
iiiiiiij

在这种情况下，最终“c”排的“第8”名选手可能会与“d”排的“第8”名选手比赛，但他们实际上是同一队的。你可能会想办法把“c”排的“第8名”球员移到“c”排的另一个位置。但是，当你在这一固定的道路上，你可以使用回溯算法，而不是反正。
通过回溯，您可以强制执行所有组合，并在发现解决方案不起作用时跳过一个组合。检查上面的URL以了解回溯（动画gif可能会有帮助）。

关于php - 生成配对组，没有重复项，php和mysql，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/45766330/