关于Lua等概率列表洗牌函数及随机种子问题的技术问询

问题1：你的解法是否正确？为何能/不能保证等概率？ #

你的代码没有正确实现Fisher-Yates洗牌，问题出在随机索引的取值范围上：
你写的是 j = math.random(1, #list)，但正确的Fisher-Yates洗牌应该是在每次循环中，从**1到当前的i（包含i）**中随机选索引j，也就是 j = math.random(1, i)。

正确实现的等概率逻辑 #

以n个元素的列表为例：

• 第一次循环（i=n）：从n个元素里随机选一个放到最后，每个元素被选中的概率是1/n；
• 第二次循环（i=n-1）：从剩下的n-1个元素里随机选一个放到倒数第二位，每个未被选中的元素此时被选中的概率是1/(n-1)，结合第一次没被选中的概率(n-1)/n，总概率是 (n-1)/n * 1/(n-1) = 1/n；
• 以此类推，每个元素最终出现在任意位置的概率都是1/n，所有排列的概率均等。

你的写法为什么会导致不等概率？ #

你的代码每次都从整个列表（1到#list）中选j，这会让元素被多次交换，破坏概率分布。比如对于4个元素的列表，总共有4^4=256种可能的交换序列，但4个元素的排列只有4!=24种，256无法被24整除，必然存在某些排列出现的次数更多，概率不均等。

常见的不等概率洗牌场景，大多是因为错误地重复从全列表选随机索引，或者交换逻辑有误（比如先选前半部分再交换，导致元素位置的概率权重不一致）。

问题2：固定math.randomseed(1)后结果为何相同？ #

Lua中的math.random是伪随机数生成器，它的工作原理是基于一个初始的“种子”值，按照固定的算法生成一系列看似随机的数。当你把种子固定为1时，每次调用math.random都会生成完全相同的序列——因为算法和初始值都没变。

所以每次调用getShuffledList时，交换用的j值序列完全一样，最终的洗牌结果自然也完全相同。通常我们会在程序启动时调用一次math.randomseed(os.time())，用当前时间作为种子，保证每次运行的随机序列不同。

你的代码 #

local printList = function (a)
  for _, value in ipairs(a) do
    io.write(value, " ")
  end
  print()
end

local interchangeElements = function(list, i , j)
  local temp
  temp = list[i]
  list[i] = list[j]
  list[j] = temp
  return list
end

local getShuffledList = function(list)
  -- math.randomseed(1) --> gives constant shuffled list on each call
  local j
  for i = #list, 1, -1 do
    j = math.random(1, #list)
    interchangeElements(list, i, j)
  end
  return list
end

printList(getShuffledList({1, 2, 3, 4}))
printList(getShuffledList({1, 2, 3, 4}))
printList(getShuffledList({1, 2, 3, 4}))
printList(getShuffledList({1, 2, 3, 4}))

输出结果 #

3 2 4 1 
3 4 2 1 
4 3 1 2 
1 2 3 4 

[Process exited 0]

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