Fischer Yates在咖啡剧本中洗牌 [英] Fischer Yates shuffle in coffee-script

问题描述

假设 Math.random（）在0和1之间产生均匀分布的随机数，这是Fischer Yates shuffle的正确实现吗？我正在寻找一个非常随机的均匀分布，其中可以指定输入数组（ arr ）中的随机元素数量（ required ）。

Assuming that Math.random() produces evenly distributed random numbers between 0 and 1, is this a correct implementation of the Fischer Yates shuffle? I am looking for a very random, even distribution, where the number of shuffled elements in an input array (arr) can be specified (as 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

推荐答案

有几件事情：

• 而不是 Math.round（），尝试 Math.floor（）;在你的
  实现 Math.round（）给出第一个元素（在索引0）
  和最后一个元素的机会比所有其他元素
  （.5 / len对比1 / len）。请注意，在第一次迭代时，您需要为 arr.length 元素输入 arr.length - 1
  
• 如果你要有一个必需的
  变量，你可以使它是可选的，因为它默认为长度的数组： shuffle =（arr，
必需= arr.length）


• 你只洗牌了最后的元素。 arr [arr.length - required ..]


• 如果必需不在范围 [0，arr.length] ？



• Rather than Math.round(), try Math.floor(); in your implementation Math.round() gives the first element (at index 0) and the last element less of a chance than all the other elements (.5/len vs. 1/len). Note that on the first iteration, you input arr.length - 1 for arr.length elements.
• If you're going to have a required variable, you might as well make it optional, in that it defaults to the length of the array: shuffle = (arr, required=arr.length)
• You return the entire array even though you only shuffled the last elements. Consider instead returning arr[arr.length - required ..]
• What if required isn't in the range [0,arr.length]?

将它们放在一起（添加一些天赋）：

Putting it all together (and adding some flair):

    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

这篇关于Fischer Yates在咖啡剧本中洗牌的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！