균일한 분포와 순진한 셔플링?

PHP 편집자 Xiaoxin은 "균일한 분포와 순진한 셔플링"의 관계를 공개합니다. 컴퓨터 과학에서 셔플링은 데이터나 컬렉션을 무작위로 추출하는 데 자주 사용되는 중요한 작업입니다. 균일 분포는 난수 분포가 특정 범위 내에서 평균임을 의미합니다. 그렇다면 셔플링을 통해 균등한 분배가 보장될 수 있을까요? 대답은 간단하지 않습니다. 따라서 이 질문을 함께 살펴보겠습니다.

질문 내용

3 int 배열을 600만 번 섞고 있습니다. 나는 배열의 각 순열을 맵에 기록합니다. 아래는 go를 사용한 코드입니다.

으아악

간단한 순서 섞기를 하고 있기 때문에 균일하게 분포된 순열을 생성해서는 안 으면 안 된다는 것을 이해했습니다. 그러나 이것이 내가 얻은 것입니다:

으아악

이는 6개의 가능한 순열이 각각 약 100만 번 발생함을 보여줍니다. 내가 얻은 분포가 균일해 보이는 이유는 무엇입니까?

EDIT: 코드를 한 번만 시드하도록 변경했습니다. 나는 이제 다음을 얻습니다:

으아악

편집 2: Hobbs 덕분에 내가 어리석은 실수를 저질렀다는 것을 깨달았습니다. 섞어야지 a，而不是 arr. 나는 이제 다음을 얻습니다:

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func randrange(min, max int) int {
    return rand.intn(max-min+1) + min
}

func naiveshuffle(arr *[3]int) {
    for i := 0; i < 3; i++ {
        e := randrange(0, 2)
        arr[e], arr[i] = arr[i], arr[e]
    }
}

func main() {
    rand.seed(time.now().unixnano())
    m := make(map[[3]int]int, 6)
    arr := [3]int{-6,10,184}

    for i := 1; i <= 6000000; i++ {
        a := arr
        naiveshuffle(&arr)
        m[a]++
    }

    for k, v := range m {
        fmt.println(k, ":", v)
    }

}

해결 방법

셔플 사이에 원래 상태로 복원하지 않고 셔플 arr을 600만 번 이상 수행했습니다. 즉, 600만 번의 시도가 독립적이지 않았습니다. 각 셔플의 순열은 고르지 않게 분포되어 있지만 이러한 순열을 서로 600만 번 쌓으면 균일에 매우 가까운 분포가 생성됩니다.

위 내용은 균일한 분포와 순진한 셔플링?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!