Fisher-Yates 셔플 을 사용하는 이 솔루션의 생각 이 잘못되었습니다 . 매번 반복 할 때마다 근사치 가 좋은 균일 한 분포를 유지하려면 (아래 편집 섹션 참조)이 기법을 사용하여 과 사이 의 값을 생성 할 수 있습니다 .0 K – 1O ( N2)

$O(N^2)$krand0

$0$k – 1

$k-1$

 // return a random number in [0..k-1] with uniform distribution
 // using a uniform random generator in [1..50]
 funtion krand(k) {
   sum = 0
   for i = 1 to k do sum = sum + RandNum50() - 1
   krand = sum mod k
 }

Fisher-Yates 알고리즘은 다음과 같습니다.

arr : array[0..99]
for i = 0  to 99 do arr[i] = i+1; // store 1..100 in the array
for i = 99 downto 1 {
  r = krand(i+1)  // random value in [0..i]
  exchange the values of arr[i] and arr[r]
}
for i = 0 to 99 do print arr[i]

편집하다:

Erick이 지적한 것처럼 krand위 의 함수는 실제로 균일 한 분포를 반환하지 않습니다. 더 나은 (임의로 더 나은) 더 빠른 근사치를 얻는 데 사용할 수있는 다른 방법이 있습니다. 하지만 (최대 내 지식) 진정으로 균일 한 분포를 얻을 수있는 유일한 방법은 사용하는 것입니다 거부 샘플링 : 선택 난수 비트와 숫자의 경우 얻을 미만입니다 반환이, 그렇지 않으면 다른 난수를 생성합니다. 가능한 구현 :r km = ⌈ 로그2( k ) ⌉

$m = \lceil \log_2(k) \rceil$아르 자형

$r$케이

$k$

function trulyrand(k) {
    if (k <= 1) return 0
    while (true) { // ... if you're really unlucky ...
      m = ceil(log_2 (k) ) // calculate m such that k < 2^m
      r = 0  // will hold the random value
      while (m >= 0) {  // ... will add m bits
        if ( rand50() > 25 ) then b = 1 else b = 0   // random bit
        r = r * 2 + b  // shift and add the random bit
        m = m - 1
      }
      if (r < k) then return r  // we have 0<=r<2^m ; accept it, if r < k
    }
}

답변

if ( rand50() > 25 ) then b = 1 else b = 0   // random bit

P = (RandNum50()-1) + (RandNum50()-1)*50^1 + (RandNum50()-1)*50^2 + ...