C实现代码如下：
void randomInPlace(int a[], int n) { int i; for (i = 0; i < n; i++) { int rand = randInt(i, n-1); swapInt(a, i, rand); } } 复制代码扩展如果上面的随机排列算法写成下面这样，是否也能产生均匀随机排列？
PERMUTE-WITH-ALL( A , n ) for i ←1 to n do swap A[i] ↔A[RANDOM(1 , n )] 复制代码注意，该算法不能产生均匀随机排列。假定 n=3，则该算法可以产生 3*3*3=27 个输出，而 3 个元素只有3!=6个不同的排列，要使得这些排列出现概率等于 1/6，则必须使得每个排列出现次数 m 满足 m/27=1/6，显然，没有这样的整数符合条件。而实际上各个排列出现的概率如下，如 {1,2,3} 出现的概率为 4/27，不等于 1/6。
排 列 概 率<1, 2, 3> 4/27
<1, 3, 2> 5/27
<2, 1, 3> 5/27
<2, 3, 1> 5/27
<3, 1, 2> 4/27
<3, 2, 1> 4/27
2.随机选取一个数字
题： 给定一个未知长度的整数流，如何随机选取一个数？（所谓随机就是保证每个数被选取的概率相等）
解1： 如果数据流不是很长，可以存在数组中，然后再从数组中随机选取。当然题目说的是未知长度，所以如果长度很大不足以保存在内存中的话，这种解法有其局限性。
解2： 如果数据流很长的话，可以这样：
如果数据流在第1个数字后结束，那么必选第1个数字。
如果数据流在第2个数字后结束，那么我们选第2个数字的概率为1/2，我们以1/2的概率用第2个数字替换前面选的随机数，得到新的随机数。
......
如果数据流在第n个数字后结束，那么我们选择第n个数字的概率为1/n，即我们以1/n的概率用第n个数字替换前面选的随机数，得到新的随机数。
一个简单的方法就是使用随机函数 f(n)=bigrand()%n，其中 bigrand() 返回很大的随机整数，当数据流到第 n 个数时，如果 f(n)==0，则替换前面的已经选的随机数，这样可以保证每个数字被选中的概率都是 1/n。如当 n=1 时，则 f(1)=0，则选择第 1 个数，当 n=2 时，则第 2 个数被选中的概率都为 1/2，以此类推，当数字长度为 n 时，第 n 个数字被选中的概率为 1/n。代码如下(注：在 Linux/MacOS 下，rand() 函数已经可以返回一个很大的随机数了，就当做bigrand()用了)：
void randomOne(int n) { int i, select = 0; for (i = 1; i < n; i++) { int rd = rand() % n; if (rd == 0) { select = i; } } printf("%d\n", select); } 复制代码3.随机选取M个数字题： 程序输入包含两个整数 m 和 n ，其中 m<n，输出是 0~n-1 范围内的 m 个随机整数的有序列表，不允许重复。从概率角度来说，我们希望得到没有重复的有序选择，其中每个选择出现的概率相等。
解1： 先考虑个简单的例子，当 m=2，n=5 时，我们需要从 0~4 这 5 个整数中等概率的选取 2 个有序的整数，且不能重复。如果采用如下条件选取：bigrand() % 5 < 2，则我们选取 0 的概率为2/5。但是我们不能采取同样的概率来选取 1，因为选取了 0 后，我们应该以 1/4 的概率来选取 1，而在没有选取 0 的情况下，我们应该以 2/4 的概率选取 1。选取的伪代码如下：
select = m remaining = n for i = [0, n) if (bigrand() % remaining < select) print i select-- remaining-- 复制代码只要满足条件 m<=n，则程序输出 m 个有序整数，不多不少。不会多选，因为每选择一个数，select--，这样当 select 减到 0 后就不会再选了。同时，也不会少选，因为每次都会remaining--，当 select/remaining=1 时，一定会选取一个数。每个子集被选择的概率是相等的，比如这里5选2则共有 C(5,2)=10 个子集，如 {0，1}，{0，2}...等，每个子集被选中的概率都是 1/10。
更一般的推导，n选m的子集数目一共有 C(n,m) 个，考虑一个特定的 m 序列，如0...m-1，则选取它的概率为m/n * (m-1)/(n-1)*....1/(n-m+1)=1/C(n,m)，可以看到概率是相等的。
Knuth 老爷爷很早就提出了这个算法，他的实现如下：
void randomMKnuth(int n, int m) { int i; for (i = 0; i < n; i++) { if ((rand() % (n-i)) < m) { printf("%d ", i); m--; } } } 复制代码