简单点来说，就是有 n 个数， 随机取 m 个，并保持有序。
解法:
我们知道了 n 和 m，轮流判断 n 个数组成的列表中每个数的概率(m/n)，每次判断后n=n-1，若当前被判断的数被选择，则m=m-1，否则 m 不变。
假设 5 个数选 2 个，那么意味着每个数的概率都是 2/5 。我们以 2/5 的概率去判断第 1 个数，那么结果有两种，选择1，不选择。当判断第 2 个的时候，在以选择了第 1 个数的情况下，选择 2 的概率是 (2-1)/(5-1)=1/4，在以没选择第 1 个数的情况下，选中 2 的概率是 2/(5-1)=2/4，所以第二个数的概率：(2/5)*(1/4) + (3/5)*(2/4) = 2/5。第二个数的概率和第一个数的概率相等。
证明:
实现:
# Python
import random
# 抽样，从n个中抽m个
def sampling(lists, m, n=None):
selected = []
if n is None:
n = len(lists)
remaining = n-1
for i in range(n):
# random.random()返回 0 ~ 1的随机数
if random.random() * remaining < m:
selected.append(lists[i])
m -= 1
remaining -= 1
return selected
# test
lists = [i for i in range(10)]
print sampling(lists, 3)
# 结果
>>>[4, 5, 7]
2. 在不知道总数的情况下随机选一个
如何从 n 个对象（可以依次看到这 n 个对象，但事先不知道 n 的值）中随机选取一个？例如，如何在事先不知道文本行数的情况下读取该文件，从中随机选择并输出一行？
解法:
我们先设一个变量叫selected，选择第 1 行赋值给 selected，并以 1/2 的概率选择第 2 行并重新赋值给selected， 以 1/3 的概率选择第 3 行并重新赋值给selected。在这以过程结束时， 每一行的选中概率都是相等的（都是 1/n， 其中 n 是文件的总行数）
要证明这个概率可以从最后一行算起,设最后一行的概率为P(n)=1/n, 倒数第二行的概率为P(n-1)=(1-P(n))*(1/(n-1)) = 1/n,倒数第m-1行概率为：
代码：
# Python
import random
def getRandLine(text):
i = 1
selected = ""
for line in text.splitlines():
if (random.random() < (1.0/i)):
selected = line
i += 1
return selected
# test
text = """
line1
line2
line3
line4
line5
line6
line7
line8
line9
line10
"""
print getRandLine(text)
# 结果
>>>line9
参考: 编程珠玑
