반복 되 지 않 는 난수 생 성

우 리 는 앞의 몇 절 에서 0 에서 n - 1 사이 에 있 는 k 개의 서로 다른 무 작위 순서의 무 작위 정 수 를 어떻게 생 성 하 는 지 세 가지 방안 을 소개 했다.[클릭 하 세 요] 본 절 은 상기 에서 다음 과 같은 문 제 를 확대 한 다음 에 몇 가지 방안 을 제시 합 니 다.
문제 설명
[0, n) 범위 내 중복 되 지 않 는 난수 가 발생 합 니 다.
프로젝트 1: Knuth 의 S 프로젝트
한 가지 결론 이 있 습 니 다: r 중간 확률 로 s 개 를 선택 하고, 한 개 를 선택 할 확률 은 s / r 입 니 다. 증명: r 에서 s 개 를 선택 하면 C (r, s) 가 있 고, 그 중에서 C (r, s) 는 조합 을 표시 합 니 다. 같은 이치 로 t 를 선택 하려 면 낳 은 (r - 1) 항목 에서 선택 (s - 1) 항목 을 선택 하고, C (r - 1, s - 1) 상황 이 있 습 니 다. r 항목 에서 s 항목 을 선택 하고, t 가 선택 되 는 확률 은 P = C (r - 1, s - 1) / C 입 니 다.(r, s); 다른 한편 으로 는 배열 조합의 성질 이 있 는데 C (r, s) = r! / (s! * (r - s)!) 는
　　C(r - 1, s - 1) = (r-1)!/( (s-1)! * (r-s)! ) = s/r * r/s * (r-1)!/( (s-1)! * (r-s)! )                             = s/r * r*(r-1)! / ( s*(s-1)! * (r-s)!) = s/r * r!/( s! *(r-s)! ) = s/r * C(r, s)
그러므로 P = s / r
의사 코드

for i = [0, n)
     if bigrand()%r < s then
        print i
        --s;
--r;

예 를 들 어 n = 5, m = 2 는 첫 번 째 원 소 를 선택 할 확률 이 2 / 5 이다. 만약 에 선택 하면 두 번 째 원 소 를 선택 할 확률 이 1 / 4 이다. 그렇지 않 으 면 두 번 째 원 소 를 선택 할 확률 은 2 / 4 이다.

void gen_knuth(int n, int m){
	for(int i = 0; i < n; i ++){
		if(big_rand()%(n-i) < m){
			cout << i;
			m--;	
		}
	}
	cout<< endl;
}

프로젝트 2: Knuth 교체 방법 P
먼저 하나의 배열 순서 로 [0, n) 의 데 이 터 를 저장 한 다음 에 무 작위 로 두 개의 아래 표 시 된 요 소 를 교환 한 다음 에 최초의 m 개 를 취하 여 m 개의 서로 다른 무 작위 수 를 기억 합 니 다.

for i = [0, n)
     x[i] = i;

for i = [0, m)
     swap(i, randint(i, n-1))

방안 3: 저수지 방법
저수지 방법 은 n 이 크 거나 n 이 알 수 없 는 상황 을 해결 하 는 데 쓰 인 다. k 를 저수지 용량 으로 보고 n = length (S) 는 사전에 알 수 없 는 집합 S 의 크기 로 본다.

array R[k];    // result 
integer i, j;  // fill the reservoir array 
for each i in 1 to k 
    do     R[i] := S[i] done;  // replace elements with gradually decreasing probability 
for each i in k+1 to length(S) 
    do     j := random(1, i);   // important: inclusive range     
        if j <= k then         
             R[j] := S[i]     
         fi 
    done

개인 적 인 이 해 는 문서 가 비어 있 지 않 으 면 (최소한 한 줄 이 있 음) 이 줄 을 적 고 문 서 를 다 읽 었 는 지 확인 하 는 것 이다. (while more input lines 에 대응 하 는) 현재 줄 이 k 줄 이면 1 / k 확률 (1 에서 k 줄 을 함께 놓 는 것 과 같은 확률 선택) 로 마지막 선택 결 과 를 k 줄 로 바 꿀 지 여 부 를 결정 하 는 것 이다. 한 번 유추 한 결과 array R [1]저 장 된 [0, n) 의 무 작위