[표 1.4.5]는 m이 6이고 n이 16일 때 메인 루프가 반복될 때마다 perm[] 배열의 내용이 어떻게 바뀌는지 보여준다. 이미 샘플링하지 않은 항목들 중에서 공평하게 무작위 r 값을 추출하면 반복을 모두 마친 후 perm[0]에서 perm[m-1]에는 균일한 무작위 샘플이 들어가게 된다(여러 번 움직이는 항목이 생길 수는 있다).
▼ 표 1.4.5 python3 sample.py 6 16의 트레이스
|
i |
r |
perm[] |
|
||||||||||||||||
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
||
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|
|
0 |
9 |
|
9 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
0 |
10 |
11 |
12 |
13 |
14 |
15 |
|
|
1 |
5 |
|
9 |
5 |
2 |
3 |
4 |
1 |
6 |
7 |
8 |
0 |
10 |
11 |
12 |
13 |
14 |
15 |
|
|
2 |
13 |
|
9 |
5 |
13 |
3 |
4 |
1 |
6 |
7 |
8 |
0 |
10 |
11 |
12 |
2 |
14 |
15 |
|
|
3 |
5 |
|
9 |
5 |
13 |
1 |
4 |
3 |
6 |
7 |
8 |
0 |
10 |
11 |
12 |
2 |
14 |
15 |
|
|
4 |
11 |
|
9 |
5 |
13 |
1 |
11 |
3 |
6 |
7 |
8 |
0 |
10 |
4 |
12 |
2 |
14 |
15 |
|
|
5 |
8 |
|
9 |
5 |
13 |
1 |
11 |
8 |
6 |
7 |
3 |
0 |
10 |
4 |
12 |
2 |
14 |
15 |
|
|
|
|
|
9 |
5 |
13 |
1 |
11 |
8 |
6 |
7 |
3 |
0 |
10 |
4 |
12 |
2 |
14 |
15 |
|
배열을 바로 바꾸지 않고 조합을 명시적으로 계산하는 이유는 이 조합을 이용해 어떠한 배열에서도 조합을 배열의 인덱스로 사용해 무작위 샘플을 구할 수 있기 때문이다. 이렇게 하면 배열을 실제로 재배치하는 것보다 좋은 경우가 종종 있다. 어떤 이유로 (예를 들어 알파벳 순서로 정렬된 고객 명단에서 무작위로 샘플을 추출하고자 하는 경우 등) 배열 자체는 원래의 순서대로 유지해야 하는 경우들이 있기 때문이다. 이 기법이 어떻게 작동되는지 생각해보기 위해, deck[] 배열에서 무작위로 포커 게임을 위한 5장의 카드를 꺼낸다고 생각해보자. m = 5, n =52로 놓고 sample.py의 코드를 실행하고 stdio.write() 문장 안의 perm[i]를 deck[perm[i]]로 바꾸면 다음과 같은 결과를 출력할 수 있다(write() 대신 writeln()을 사용한다).
3 of Clubs Jack of Hearts 6 of Spades Ace of Clubs 10 of Diamonds