1

Math.random()0 と 1 の間で均等に分散された乱数を生成すると仮定すると、これはフィッシャー イェーツ シャッフルの正しい実装ですか? 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
4

1 に答える 1

1

いくつかのこと：

  • ではなくMath.round()、試してみてくださいMath.floor()。あなたの実装でMath.round()は、最初の要素 (インデックス 0) と最後の要素は、他のすべての要素 (.5/len 対 1/len) よりも可能性が低くなります。最初の反復では、要素を入力arr.length - 1することに注意してください。arr.length
  • required 変数を使用する場合は、デフォルトで配列の長さになるという点で、オプションにすることもできます。shuffle = (arr, required=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
于 2012-10-18T06:20:44.813 に答える