列表均匀取样？

Question

一个int类型的列表A，长度为a，从此列表中【均匀】取出长度为x的样本列表？

Answer 1

以下代码均匀随机选取样本列表b[1:k]且保持原来在a[1:n]中的顺序。算法是：p[1:n]是一个1到n的随机排列，选择那些使p[i] <= k的a[i]进入样本。

choose(a[1:n], k)
  b = {}
  p = {1, 2, ... n}
  for i from 1 to n
    // random(i, n) 返回i和n之间（包含）的随机整数
    swap(p, i, random(i, n))
    if p[i] <= k
      append a[i] to b
  return b

Answer 2

请参考蓄水池算法