Lua实现周期重复模式Fisher-Yates原地洗牌问题求解

需求说明 #

针对长度16的序列表，洗牌逻辑要求：

• 先生成1~4区间的单份随机洗牌排列
• 将该固定洗牌模式重复应用到表内1-4、5-8、9-12、13-16四个等长分段
• 触发条件为门信号上升沿（rising edge）

示例效果：原序列为{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}，若生成的4元素洗牌模式为4,2,3,1，最终输出为{4,2,3,1,8,6,7,5,12,10,11,9,16,14,15,13}。

原有代码问题 #

原有实现将随机索引生成逻辑放在全表遍历循环中，每处理一个元素就重新生成随机交换位置，导致每个分段独立生成随机排列，无法实现全分段复用同一洗牌模式的效果。另外原有代码中s = t为直接引用赋值，会直接修改原始表数据。
原有错误实现代码：

t = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

range = 4

local function ShuffleInPlace(t)
    for i = #t, 2, -1 do
    
    local j = math.random(1, range)     
    local k = (math.floor(i/(range+.001)))*range + j
                
    t[i], t[j] = t[j], t[i]
    end
end

-- initialize new table for shuffling
if s == nil then s = {} end 

-- use gate rising edge to shuffle
if prev == nil then prev = 0 end
if gate > 0 and prev <= 0 then  
    s = t
    ShuffleInPlace(s)
end

prev = gate

修正后实现 #

核心逻辑调整为两步：触发洗牌时仅生成一次单段长度的洗牌置换规则，再将这套规则无修改应用到所有分段，过程中不再生成新的随机数。

-- 原始基准序列
t = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
-- 单段长度
range = 4

-- 生成单段的标准Fisher-Yates洗牌置换规则
local function GenerateShufflePattern(segmentLength)
    local pattern = {}
    -- 初始化位置映射
    for i = 1, segmentLength do
        pattern[i] = i
    end
    -- 单段内做随机洗牌，仅执行一次
    for i = segmentLength, 2, -1 do
        local randPos = math.random(1, i)
        pattern[i], pattern[randPos] = pattern[randPos], pattern[i]
    end
    return pattern
end

-- 将固定洗牌模式应用到所有分段
local function ApplyPatternToAllSegments(targetTable, pattern, segmentLength)
    local totalSegments = #targetTable / segmentLength
    for segIndex = 0, totalSegments - 1 do
        local segBasePos = segIndex * segmentLength
        -- 缓存当前分段原始值，避免写入覆盖导致取值错误
        local segmentCache = {}
        for pos = 1, segmentLength do
            segmentCache[pos] = targetTable[segBasePos + pos]
        end
        -- 按照固定模式写入洗牌后的值
        for pos = 1, segmentLength do
            targetTable[segBasePos + pos] = segmentCache[pattern[pos]]
        end
    end
end

-- 初始化状态变量
if s == nil then s = {} end
if prev == nil then prev = 0 end

-- 门信号上升沿触发洗牌
if gate > 0 and prev <= 0 then
    -- 拷贝原始表，避免修改基准源数据
    s = {table.unpack(t)}
    -- 仅生成一次洗牌模式，所有分段复用
    local fixedShufflePattern = GenerateShufflePattern(range)
    ApplyPatternToAllSegments(s, fixedShufflePattern, range)
end

prev = gate

关键修正点 #

• 洗牌模式仅在上升沿触发时生成一次，从根源避免各分段独立随机的问题
• 处理每个分段时先缓存原始值，避免交换过程中原值被覆盖导致结果错乱
• 替换原有的直接引用赋值为表拷贝，防止原始基准序列被修改
• 严格遵循Fisher-Yates算法逻辑生成单段洗牌模式，保证单段洗牌的均匀随机性

内容的提问来源于stack exchange，提问作者jersmi