生成不重复题目-随机

需求

答题系统,允许角色每天最多答对N道题目。如果当天题库数量大于N，则要求当天答对的题目不能再出现。

糟糕的代码

以下是生成题目ID的实现大致如下，主要问题是作者没有想到很好的去重办法，侥幸以为只要尽可能多的循环次数（2倍题库数量），来降低题目再次出现的概率，然而重复的题目还是出现了，这段糟糕的代码才“有幸”见于诸位。

lua代码

-- tQuestSave 记录当天答对题目
-- iQuestListSize  题库的数量
function GenQuestId(tQuestSave, iQuestListSize)
    local iTargetQuestId = -1
    for i = 1, iQuestListSize * 2, 1 do
        iTargetQuestId = math.random(1, iQuestListSize)
        if tQuestSave[iQuestId ] == nil then
             break
        end
    end
    return iTargetQuestId 
end

优化后

通过增大循环次数的随机做法，令算法非常不稳定。N个不重复的题目最终随机分散在题库里。N个题目彼此相邻是其中一种极端情况。那么反过来想，在题库中随机在彼此相邻的N个题目中肯定有未答对的题目，算法的时间复杂度O(n)

lua代码

function GenQuestId(tQuestSave, iQuestSaveMaxSize, iQuestListSize)
    local iStartId= math.random(1, iQuestListSize)
    local iTargetQuestId = -1
    for i = 1, iQuestSaveMaxSize - 1, 1 do
         iTargetQuestId =  iStartId + i
        if tQuestSave[iTargetQuestId ] == nil then
             break
        end
    end
    return iTargetQuestId
end

原文:
https://lizijie.github.io/2021/07/17/%E7%94%9F%E6%88%90%E4%B8%8D%E9%87%8D%E5%A4%8D%E9%A2%98%E7%9B%AE-%E9%9A%8F%E6%9C%BA.html
作者github:
https://github.com/lizijie