Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • Fortran

Idiom #158 Random sublist

Create a new list y from randomly picking exactly k elements from list x.

It is assumed that x has at least k elements.
Each element must have same probability to be picked.
Each element from x must be picked at most once.
Explain if the original ordering is preserved or not.

allocate (sample(k))
do i=1,k
   sample(i) = x(i)
end do
do i=k+1,n
  call random_number(a)
  j = 1 + int(i*a)
  if (j .le. k) sample(j) = x(i)
end do

This is the R algorithm for reservoir sampling, see Wikipedia article.
(def y (->> x shuffle (take k)))

New implementation...
< >
programming-idioms.org