有一个很常见的问题：从\( N \)个互不相同的数，随机选取 \( M(M<N) \) 个数字.比如在一组N个样品当中选择其中M个进行破坏性测试。

朴素的想法是，输出 \( M \) 次随机数，在每次输出存于一个表中，每次准备输出时看一下这次要输出的随机数是否以前出现过，若出现过就再生成一个随机数，若没出现过就存入这个表并输出它。这个方法在M远小于 \( N \) 的时候是很灵的，按概率来算一般执行 \( M \) 次就可以获得 \( M \) 个不同的随机数。但是当 \( N \) 与M都很大，并且 \( M \) 和 \( N \) 相差并不很大的时候，比如从整个公司1000人当中挑随机选850人，当已经选出849人之后，只有151/1000的概率能选出一个之前未出现过的随机数，并且每次出现一个随机数要与之前849个数作比较以检查是否之前出现过，这样可能花的时间更长，下面介绍一种仅与总样本数N有关的抽样方法，这是《编程珠玑》上所讨论过的一种算法。在工程上还算实用。

我们从 \( N \) 个样本中选取M个样本，每个样本被选出的概率都是\( \frac{M}{N} \)。我们为样本编号为1到N，首先1号样本抽选的概率是 \( \frac{M}{N} \) ，我们可以用if (random(0,N) < M ) then select 1 表示\( \frac{M}{N} \)的概率。接下来选择2号样本，如果1号样本被选出了，那么2号样本被选出的概率则应是\( \frac{M-1}{N-1}\)（从剩下N-1个样本中再取M-1个），而如果1号样本没被选出，那么1号样本被选出的概率就是\( \frac{M}{N-1}\)（从剩下 \( N-1 \) 个样本里选 \( M \) 个）。这样2号样本被选出的概率为: \[ (\text{1号被选出})\cdot(\text{在1选出时选2的概率})+(\text{1未被选出})\cdot(\text{1未选时选2的概率})=\frac{M}{N}\cdot \frac{M-1}{N-1}+(1-\frac{M}{N})\cdot(\frac{M}{N-1}) =\frac{M}{N} \]

类似地可得出，每个样本被选出的概率都是\( \frac{M}{N} \)。

程序设计时，我们可以设定循环次数就是N次，每次循环时做一次随机，判断生成[0,N-i)的随机整数是否小于剩余样本数M，若小于则选择这第i个样本，同时使剩余样本数的变量减去1，否则什么也不做进行下一趟循环，直到进行完所有N趟循环。

from random import randint
N=100
M=25
for i in range(N):
	if randint(0,N-i-1)<M:
		print(i)
		M-=1

这样就可以有序的、随机不重复的从N个样本中选取M个样本