Lua中如何基于动态概率实现车辆到车位的正确分配？

原始实现代码 #

generateSlotIndex函数 #

local function generateSlotIndex(totalCars, totalSlots)
    local sum = 0
    local r = math.random()  -- 生成随机数
    local result
    for k = 1, totalSlots do
        local prob = 1
        -- 计算当前索引的概率
        for i = 1, k - 1 do
            prob = prob * (totalSlots - totalCars - i + 1) / (totalSlots - i + 1)
        end
        prob = prob * totalCars / (totalSlots - k + 1)  -- 调整第k个索引的概率
        sum = sum + prob  -- 累加概率
        if r <= sum and not result then
            result = k  -- 若随机数小于等于累加概率，将结果设为k
        end
        if sum >= 1 then break end  -- 累加概率达到1时停止循环
    end
    return result
end

getSlots函数 #

local function getSlots(totalCars, totalSlots)
    local slotIndex = 0  -- 初始化车位索引
    local restCars = totalCars  -- 剩余待分配车辆数
    local restSlots = totalSlots  -- 剩余待分配车位数
    local slots = {}  -- 存储已分配车位的表
    for carIndex = 1, totalCars do
        local index = generateSlotIndex(restCars, restSlots)  -- 生成随机车位索引
        slotIndex = slotIndex + index
        slots[slotIndex] = 1 -- 将车位索引存入列表
        restCars = restCars - 1  -- 剩余车辆数减1
        restSlots = restSlots - index  -- 剩余车位数减去当前索引值
    end
    return slots  -- 返回已分配车位列表
end

补充说明：动态概率指车辆分配至特定车位的概率取决于剩余车辆数与车位数。如10辆车、20个车位时，第一辆车更大概率分配至靠前车位；随分配推进，剩余车位概率随剩余车辆数与车位数成比例降低。正确概率权重需满足：每辆车独占一个车位，分配初期倾向靠前车位，后期逐步分散至剩余车位。

百万次仿真分析结果显示：红色曲线为车辆在所有车位的分布，蓝色曲线为首个被占用车位的索引分布（对应20个车位分配10辆车场景）。

问题解答 #

1. 需考虑的边缘场景 #

• 车辆数等于车位数：所有车位必须填满，无需概率选择，直接按顺序分配即可。
• 车辆数为0：直接返回空分配结果，避免无效计算。
• 车位数小于车辆数：抛出错误或返回无效标识，无法完成分配。
• 剩余车辆数等于剩余车位数：剩余车位必须全部分配，无需概率计算。
• 单次分配时剩余车辆数为1：仅需从剩余车位中按预期概率选一个，无需复杂迭代。

2. 概率计算逻辑修正 #

原始代码的概率建模和车位索引更新逻辑存在偏差，导致分配结果不符合预期。以下是修正后的实现：

修正后的generateSlotIndex函数

local function generateSlotIndex(restCars, restSlots)
    -- 构建权重列表：靠前车位权重更高，结合剩余车辆/车位比例动态调整
    local weights = {}
    for i = 1, restSlots do
        -- 权重公式：(剩余车位倒序位置) * (剩余车辆/剩余车位比例)
        weights[i] = (restSlots - i + 1) * (restCars / restSlots)
    end

    -- 计算权重总和
    local totalWeight = 0
    for _, w in ipairs(weights) do
        totalWeight = totalWeight + w
    end

    -- 随机选择对应索引
    local r = math.random() * totalWeight
    local currentSum = 0
    for i = 1, restSlots do
        currentSum = currentSum + weights[i]
        if r <= currentSum then
            return i
        end
    end

    return restSlots -- 兜底返回最后一个车位
end

修正后的getSlots函数

local function getSlots(totalCars, totalSlots)
    -- 边缘场景预处理
    if totalCars <= 0 then return {} end
    if totalCars > totalSlots then error("车辆数不能超过车位数") end

    local usedSlots = {}  -- 标记已使用车位
    local slots = {}
    local restCars = totalCars
    local restSlots = totalSlots

    for _ = 1, totalCars do
        -- 生成剩余可用车位的相对索引
        local relIndex = generateSlotIndex(restCars, restSlots)
        -- 映射为实际车位编号（跳过已使用车位）
        local actualIndex = 0
        local count = 0
        while count < relIndex do
            actualIndex = actualIndex + 1
            if not usedSlots[actualIndex] then
                count = count + 1
            end
        end
        -- 标记并记录分配结果
        usedSlots[actualIndex] = true
        slots[actualIndex] = 1
        -- 更新剩余数量
        restCars = restCars - 1
        restSlots = restSlots - 1
    end

    return slots
end

修正逻辑说明：

• 权重计算：靠前车位权重随位置倒序线性递增，同时结合剩余车辆与车位的比例动态调整概率强度，符合“初期靠前、后期分散”的需求。
• 索引映射：通过遍历跳过已使用车位，将相对索引转换为实际车位编号，解决了原始代码中连续分配的错误。
• 边缘场景提前处理：避免无效计算和逻辑错误。

3. Lua中更优的动态概率分配方案 #

方案一：权重选择优化（二分查找）

针对大规模仿真场景，使用二分查找优化权重选择的时间复杂度（从O(n)降至O(logn)）：

local function weightedRandomSelect(weights)
    local prefixSums = {}
    local total = 0
    for _, w in ipairs(weights) do
        total = total + w
        table.insert(prefixSums, total)
    end
    local r = math.random() * total
    -- 二分查找定位索引
    local low, high = 1, #prefixSums
    while low < high do
        local mid = math.floor((low + high)/2)
        if prefixSums[mid] < r then
            low = mid + 1
        else
            high = mid
        end
    end
    return low
end

-- 整合到generateSlotIndex
local function generateSlotIndex(restCars, restSlots)
    local weights = {}
    for i = 1, restSlots do
        weights[i] = (restSlots - i + 1) * (restCars / restSlots)
    end
    return weightedRandomSelect(weights)
end

方案二：可用车位池直接模拟

维护可用车位列表，每次按权重随机移除元素，逻辑直观易调试，适合中小规模场景：

local function getSlots(totalCars, totalSlots)
    if totalCars <=0 then return {} end
    if totalCars > totalSlots then error("车辆数超量") end

    -- 初始化可用车位列表
    local available = {}
    for i = 1, totalSlots do
        table.insert(available, i)
    end

    local slots = {}
    for _ = 1, totalCars do
        local restCars = totalCars - _ + 1
        local restSlots = #available
        -- 计算每个可用车位的权重
        local weights = {}
        for idx, slot in ipairs(available) do
            weights[idx] = (totalSlots - slot + 1) * (restCars / restSlots)
        end
        -- 选择并移除车位
        local selectIdx = weightedRandomSelect(weights)
        local selectedSlot = table.remove(available, selectIdx)
        slots[selectedSlot] = 1
    end
    return slots
end

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