RandNum50
1-50 범위의 균일 한 난수를 생성하는 난수 생성기가 제공됩니다. 이 난수 생성기 만 사용하여 1에서 100까지의 모든 정수를 임의의 순서로 생성하고 인쇄 할 수 있습니다. 모든 숫자는 정확히 한 번만 와야하며 어느 위치에서나 발생할 수있는 확률은 같아야합니다.
가장 효율적인 알고리즘은 무엇입니까?
답변
Fisher-Yates 셔플 을 사용하는 이 솔루션의 생각 이 잘못되었습니다 . 매번 반복 할 때마다 근사치 가 좋은 균일 한 분포를 유지하려면 (아래 편집 섹션 참조)이 기법을 사용하여 과 사이 의 값을 생성 할 수 있습니다 .0 K – 1
O(N2) 0k−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 k
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
}
}
답변
다른 사람들이 불확실한 수의 이탈을 취하는 것과 관련된 대략적인 솔루션과 솔루션을 제공했기 때문에 유한 한 횟수의 RandNum50()
호출 만 필요로하는 알고리즘이 없다는 증거 는 어떻습니까?
다른 사람들이 지적했듯이, 1-100의 숫자를 임의의 순서로 인쇄하는 것은 이러한 숫자의 임의 순열을 인쇄하는 것과 같습니다. 100이 있습니다! 이러한 순열 중 하나이므로 특정 순열은 확률 로 출력되어야합니다.
1100!k
RandNum50
k
RandNum50
k
RandNum50
150k
c50k
c
1100!
100!
50k
k
100!
50k
답변
nlogn+O(1)
if ( rand50() > 25 ) then b = 1 else b = 0 // random bit
1
n! 1
2
3
n
해당 게시물에서 제안한대로 임의의 비트에서 유니폼을 생성하는 방법을 모르는 경우 이러한 방식으로 유니폼의 근사값을 직접 생성 할 수도 있습니다 (Vor의 “trulyrand”와 동일하지만 더 빠름).
P = (RandNum50()-1) + (RandNum50()-1)*50^1 + (RandNum50()-1)*50^2 + ...
P
50
P
Q=Pmodn
P > n
n=100!P>n
답변
나는 확인하기 위해 분석을 수행하지 않은 방법 균일 한 (또는하지 않음)이 될 것, 진정한 셔플로 조정 할 수 있지만, 당신은 단지의 시작 배열에서 선택할 수 i
= 일 지수 i + 1
는 (k + RandNum50() + RandNum50() - 1) mod (100 - k)
와, 인덱스를 제거, k
= 0..99?
이것은 RandNum50() + RandNum50()
분포 의 피크를 균일하게 앞으로 “밀어냅니다” .
0 인덱스 (1)을 첫 번째 선택에서 얻을 수 없으며 0을 생성하는 대안 1..50 + 1..50 조정을 신속하게 볼 수 없기 때문에 이것이 언급 한대로 이것이 옳지 않다고 확신합니다. ..99.
최신 정보
내가 언급 한 문제를 해결하기 위해 RandNum100
첫 번째 k
오프셋 을 무작위로 초기화하기 위해 질문 의견에 언급 된 것처럼 효과적으로 사용 했습니다 .
이것은 정면에 큰 파도가있는 분포를 생성합니다.
1 RandNum50
씩 전진하는 대신 다른 것을 사용 하여 먼저 증가 시켰습니다 k
. 이것은 나에게 충분한 무작위 결과를 생성하지만 K를 2로 변경하면 쉽게 볼 수 있듯이 여전히 “정확하지 않은”무작위는 아닙니다.
K를 수용 한 VB.NET 코드 테스트 . 실제로 O (K), 6K + 2입니다.