javascript - Fischer Yates 以 CoffeeScript 洗牌

Question

假设 Math.random() 生成 0 到 1 之间均匀分布的随机数，这是 Fischer Yates shuffle 的正确实现吗？我正在寻找一个非常随机、均匀的分布，其中可以指定输入数组 (arr) 中的已打乱元素的数量(作为 required)。

shuffle = (arr, required)->
  rnd = (int) ->
    r = Math.random() * int
    Math.round r

  len = arr.length-1

  for i in [len..1]
    random = rnd(i)
    temp = arr[random]
    arr[random] = arr[i]
    arr[i] = temp
    break if i < len - (required - 2)

  return arr

Answer 1

有几件事:

• 尝试使用Math.floor()，而不是Math.round()；在你的实现 Math.round() 给出第一个元素(索引 0 处)最后一个元素的机会比所有其他元素都要小(0.5/len 与 1/len)。请注意，在第一次迭代时，您为 arr.length 元素输入 arr.length - 1。
• 如果您需要必需变量，您也可以将其设为可选，因为它默认为数组的长度: shuffle = (arr,
必需=arr.length)
• 即使您只打乱了最后一个元素，您也会返回整个数组。考虑返回 arr[arr.length - required ..]
• 如果 required 不在 [0,arr.length] 范围内怎么办？

将它们放在一起(并添加一些天赋):

    shuffle = (arr, required=arr.length) ->
      randInt = (n) -> Math.floor n * Math.random()
      required = arr.length if required > arr.length
      return arr[randInt(arr.length)] if required <= 1

      for i in [arr.length - 1 .. arr.length - required]
        index = randInt(i+1)
        # Exchange the last unshuffled element with the 
        # selected element; reduces algorithm to O(n) time
        [arr[index], arr[i]] = [arr[i], arr[index]]

      # returns only the slice that we shuffled
      arr[arr.length - required ..]

    # Let's test how evenly distributed it really is
    counter = [0,0,0,0,0,0]
    permutations = ["1,2,3","1,3,2","2,1,3","2,3,1","3,2,1","3,1,2"]
    for i in [1..12000]
      x = shuffle([1,2,3])
      counter[permutations.indexOf("#{x}")] += 1

    alert counter