如何选取等概率不重复的随机数？

今天看到了一道腾讯的面试题：从 1000 个不重复的数字中随机抽取 900 个不重复的数字，要保证概率相等，不可以重复取。

在看到这道题的时候，总感觉有些无力。要保证概率相同，还不可以重复取，这就使得随机数不再那么的 “随机” 了。问题就变成了如何选取等概率不重复的随机数。当时的第一思路就是将选过的数字置为 -1 ，表示已选过，如果再次选到的话，就重新随机选取，直到选出未选过的数字。但是这就会产生问题：对于每一次选择来看，确实是等概率的，但是综合来看，后面的数字的选取次数会多很多次，这一点，我就不太确定是否仍然保持等概率了；而且，越到后面，遇到已选过的元素的可能性越高，重复选取次数就越多，效率也就可想而知。

后来看到了一个不错的想法：按顺序产生这些数，但随机产生它们的位置。

int a[1000];
for(int i = 0; i < 1000; i++)
    a[i] = i;
for(int i = 0; i < 1000; i++)
    swap(a[i], a[rand()%1000]);

这个想法很巧妙地生成了等概率的随机序列，然后选取前 900 个元素即可（当然你也可以花式选择元素）。这样既保证了效率，也让随机数真正的 “随机” 了。因为即使重复也属于概率意义上的正常情况。

当然对于这个问题，也可以逆向思维：随机选取 100 个不要的数字，剩下的数字打乱顺序后就是我要的结果。这个方法可以大大简化第一种方法，适用于范围数组与目标数组的大小非常接近的情况。

参考资料：
【转】如何高效产生m个n范围内的不重复随机数（m<=n)