Fischer Yates가 커피 스크립트에서 뒤섞음

Question

Math.random()이 0에서 1 사이의 균등하게 분포 된 난수를 생성한다고 가정하면, 이것이 Fischer Yates 셔플의 올바른 구현입니까? 아주 무작위이고 균일 한 분포를 찾고 있는데, 입력 배열 (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.round(), Math.floor()을 시도; 구현에서 Math.round()은 첫 번째 요소 (색인 0)가 이고 나머지 요소가 다른 모든 요소보다 (0.5/len 대 1/len)보다 적은 확률을 나타냅니다. 첫 번째 반복에서는 arr.length 요소에 arr.length - 1을 입력합니다.
• 당신이 required 변수를 가질 거라면, 당신은뿐만 아니라 배열의 길이에 그것이 기본적으로, 그것은 선택 할 수 있습니다 당신은 당신이 마지막을 단행하더라도 전체 배열을 반환 shuffle = (arr, required=arr.length)
• 집단. 대신 반환 고려하십시오
• 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