어떻게 $U ni f (0, 1)$ 값을 생성하는 함수를 가지고 있을때, 순열을 어떻게 랜덤하게 샘플링할 수 있을까?

순열 랜덤 셔플 알고리즘이 중간까지만 진행해도, 여태까지 스왑한 부분은 알고리즘 종료까지 수정하지 않고, 그 부분은 균등 분포를 따른다는걸 잘 생각해보면 순열 랜덤 셔플 알고리즘을 중간에서 끊음으로 만들 수 있다.

알고리즘

어떤 순열 $P_{1}, P_{2}, \dots P_{n}$ 이 있고, $M$ 개를 샘플링 하고싶다고 하자.
k = n 으로 두고 시작한다.
$U \sim U ni f (0, 1)$ 일때 $I = ⌈ k U ⌉$ 라고 하자. $U$ 를 생성해서 $I$ 를 구한다.
$P_{i}$ 와 $P_{k}$ 를 바꾼다.
$k := k - 1$ 을 하고, 만일 $n - k \geq M$ 이라면, 3으로 돌아간다. 아니라면 멈춘다.

코드

import random
 
r = random.random
 
def random_sample(lst, m):
    n = len(lst)
    tmp = lst[:]
    for i in range(n, n-m, -1):
        j = int(r() * i)
        tmp[i-1], tmp[j-1] = tmp[j-1], tmp[i-1]
 
    return tmp[:-m]
 
l = list(range(10))
print(random_sample(l, 5))