SQL查询来获取随机未使用组合

我想创建一个可以运行的1对1的对决比赛的数据库。它需要跟踪谁赢了，输了每场比赛以及关于比赛的任何评论，以及随机决定下一场比赛。

规则：

有玩家x个。每个玩家最终都会玩其他玩家一次，实际上覆盖了所有可能的玩家独特组合。

数据库表（样本数据）：

DECLARE @Players TABLE (
    ID INT PRIMARY KEY IDENTITY, 
    Name VARCHAR(50) 
) 

ID Name 
-- ----- 
1 Alex 
2 Bob 
3 Chris 
4 Dave 

DECLARE @Matches TABLE (
    ID INT PRIMARY KEY IDENTITY, 
    WinnerId INT, 
    LoserId INT 
) 

ID WinnerId LoserId 
-- -------- ------- 
1 1  2  
2 4  2  
3 3  1  

DECLARE @Comments TABLE (
    ID INT PRIMARY KEY IDENTITY, 
    MatchId INT, 
    Comment VARCHAR(MAX) 
) 

ID MatchId Comment       
-- ------- ------------------------------ 
1 2  That was a close one.   
2 3  I did not expect that outcome.

问题：

我怎样才能有效地查询得到一个随机匹配了尚未发生的？

主要问题是玩家的数量会随着时间的推移而增长。现在在我的例子数据中，我只有4名球员出现了6次可能的比赛。

Alex,Bob 
Alex,Chris 
Alex,Dave 
Bob,Chris 
Bob,Dave 
Chris,Dave

这将是小到足以简单地保持抓住对应于玩家的ID 2张随机数，然后检查对决表，如果已经发生的对决。如果它有：再获得2个并重复该过程。如果它还没有用作下一场比赛。但是，如果我有10,000名球员，可能会有49995000次比赛，并且它会变得太慢。

任何人都可以在正确的方向指向我更高效的查询吗？如果这能帮助提高效率，我愿意改变数据库设计。

来源

2012-04-22 JohnMcCon

这是哪个DBMS的用途？ – 2012-04-22 22:18:24

如果你尽一切可能的配对和那些已经玩过之间的外连接，然后过滤掉已经被播放了的，你留下了尚未被播放配对。选择随机之一是排序然后一个简单的情况：

SELECT p1.Name, p2.Name FROM 
    Players p1 
    JOIN Players p2 ON (
    p1.ID < p2.ID 
) 
    LEFT JOIN Matches ON (
     (WinnerId = p1.ID AND LoserId = p2.ID) 
    OR (WinnerId = p2.ID AND LoserId = p1.ID) 
) 
WHERE Matches.ID IS NULL 
ORDER BY RAND() 
LIMIT 1;

EDIT

正如下面所指出的，上述LIMIT语法是MySQL的特定。您可能需要使用SQL实现的适当语法 - 让我们知道它是什么，如果需要，可以提供建议。我知道在Microsoft SQL Server中使用TOP和Oracle ROWNUM，但是否则您的Google搜索可能与我的一样好。 :)

来源

2012-04-22 21:46:20 eggyal

我给出了更好的答案。删除我的并且赞成你的。 – JohnFx 2012-04-22 21:47:19

'LIMIT'？这个问题没有被标记为MySQL。 – 2012-04-22 22:17:26

@ypercube：不错的地方。我已经更新了这一点。 – eggyal 2012-04-22 22:25:33

尽管数据集很大，但只要返回一个密钥，使用limit密钥就会停止进行其他处理。一种可能性是使用下面的查询来返回下一个匹配。

SELECT * FROM Players p1, Players p2 WHERE p1.ID <> p2.ID AND (p1.ID, p2.ID) NOT IN (Select WinnerID, LoserID FROM Matches) AND (p2.ID, p1.ID) NOT IN (Select WinnerID, LoserID FROM Matches) LIMIT 1

来源

2012-04-22 21:45:15

我想知道为什么你需要随机选择2名球员。如何在前面生成可能匹配的整个列表，然后添加一个WinnerId列？对于下一场比赛，只需选择没有WinnerId设置的第一行。

来源

2012-04-22 21:50:07 NaN

对于您的问题，您希望A）以随机顺序考虑玩家B的所有2元素子集。

对于A，其他答案是建议使用SQL连接与各种条件。如果您真的需要处理10,000个玩家，则数据库密集度较低的解决方案可能是使用高效组合生成算法。我发现以前的答案列出了一些来自TAOCP vol。 4 here。对于2元的子集的情况下，一个简单的双循环嵌套在玩家ID词典编纂顺序就可以了：

for player_a in 1..num_players: 
    for player_b in player_a+1..num_players: 
    handle a vs. b

B部分，你可以使用第二个表映射玩家1..n到整数1..n的洗牌。保持这个混洗映射，直到完成锦标赛过程。您可以使用Knuth-Fisher-Yates shuffle。

为了跟踪您在这个问题的实例中的位置，您可能需要定期将组合生成器的状态保存到数据库。这可能比从单独的原始表格中确定序列的位置要快。

正如你所提到的那样，通过这种方式处理10,000名对手的比赛结果将导致将近五千万对阵处理。你可能会考虑一个不需要每个玩家与其他玩家竞争的比赛结构。例如，如果A击败B和B击败C，那么您可能不必考虑A是否击败C.如果适用于您的场景，那种快捷方式可以节省大量时间。

来源

2012-04-22 22:29:01

SQL查询来获取随机未使用组合

回答

相关问题