Lua中如何实现Fisher-Yates搅拌算法

2016-2-23 9:50:5
收藏：0
阅读：79
评论：2

我一直在寻求关于随机数的问题，决定使用Fisher-Yates搅拌算法是最佳选择。我创建了一个表't'

t = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

现在，我该如何将它们搅拌并能够单独使用它们，例如在另一个表'u'中生成结果

u = {}
点赞
用户1190388
用户1190388

注意：请查看另一个答案 https://stackoverflow.com/a/68486276/1190388，它解决了下面代码片段中的问题，并提供了其他替代方案

如果表中没有空洞：

math.randomseed(os.time()) -- 确保结果始终不同
function FYShuffle( tInput )
    local tReturn = {}
    for i = #tInput, 1, -1 do
        local j = math.random(i)
        tInput[i], tInput[j] = tInput[j], tInput[i]
        table.insert(tReturn, tInput[i])
    end
    return tReturn
end
2016-02-23 09:46:43
用户3554391
用户3554391

对于那些后来发现这个答案的人，这将在原地进行洗牌而不制作新表：

local function ShuffleInPlace(t)
    for i = #t, 2, -1 do
        local j = math.random(i)
        t[i], t[j] = t[j], t[i]
    end
end

而这一个则返回一个洗牌后的表而不会修改原始表（不像当前答案，它既原地洗牌又返回一个副本）：

local function Shuffle(t)
    local s = {}
    for i = 1, #t do s[i] = t[i] end
    for i = #t, 2, -1 do
        local j = math.random(i)
        s[i], s[j] = s[j], s[i]
    end
    return s
end

用法：

local t = {"a", "b", "c", "d", "e", "f"}

print(table.concat(t)) --> abcdef

local s = Shuffle(t)

print(table.concat(t)) --> abcdef（未改变）
print(table.concat(s)) --> fbcade（洗牌）

ShuffleInPlace(t)

print(table.concat(t)) --> dcbfea（洗牌）

并快速检查它们是否均匀：

local t = {"a", "b", "c"}

local results = {abc = 0,acb = 0,bac = 0,bca = 0,cab = 0,cba = 0}

for i = 1, 10000000 do
    ShuffleInPlace(t)
    local r = table.concat(t)
    results[r] = results[r] + 1
end

for k, v in pairs(results) do print(k, v) end

--[[
cba 1667473
cab 1666235
bca 1665672
bac 1666782
acb 1666447
abc 1667391
--]]
2021-07-22 14:06:17

作者:

用户5957310

用户5957310
推荐文章