簡單點來說，就是有 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
參考: 編程珠璣
