排序算法中的循环不变式中总结了循环不变式在排序算法中的运用，循环不变式还可以用于随机算法，本文总结循环不变式在随机算法中的运用。
随机算法
随机算法的数学基础是概率论，如果我们能够证明某个算法服从特定的概率公式，那么我们可以认为此算法具备均匀随机分布的特征。
问题：如何产生随机数
给定一个有序的输入，如A[1…n]，如何通过一个算法，输入有序的A，返回一个A的集合Ua，Ua中的所有子序列是均匀随机分布的。
思路
我们确定序列A[1…n]是排列P(n,n)序列集合中的某一个子序列，而排列P(n,n)的所有子序列是符合随机均匀分布的。假设特定的子序列[a1,a2,…an]被包含在P(n,n)集合中的事件为E(x)，那么E(x)发生的概率为：
\frac{1}{n!}
因此将A[1…n]转变随机均匀分布的方法是求得A[1…n]的所有子序列，然后随机取一个。
解法1
伪代码
def premute_sorting(A):
n = len(A)
# 从P(n,n)中随机选择一个子序列
P[n] <- 0
for i = 0 to n:
P[i] = random(1, n**3)
# 以P[1...n]为key，将A[1...n]排序
# 使用选择排序法
for i = 1 to n:
for j = i to n:
# 从j到n序列中找到一个最小值所在位置k
# 交换P[i]与P[k]的值
# 交换A[i]与A[k]的值
循环不变式
算法本身就是一个选择排序算法，但是我们这里需要证明的是通过排循一个随机的无序序列P[1…n]过程中产生的数组下标序列Index[1…k]是随机均匀分布的，因此循环不变式为：在i=1 to n的循环中，序列Index[1…k]为P(n,k)排列序列集合中的一个子序列的概率:
\frac{(n-k)!}{n!}
证明
初始i=1
当i=1时，此时Index[1]的值为随机序列P(n,1)中的一个值，Index[1]的值为[1,n]的某个值的概率为:
\frac{(n-1)!}{n!}=\frac{1}{n}
不变式成立。
保持
假设当i=m时，序列Index[1…m]为P(n,m)排列序列集合中的一个子序列的概率**:
\frac{(n-m)!}{n!}
当i=m+1时，序列Index[1…m,m+1]是P(n,m+1)排列序列集合中的一个子序列的概率是多少？ 我们设定序列Index[1…m]为P(n,m)的一个子序列的事件为E1，概率为P(E1)。此时事件E1已经发生，再假定在E1已经发生了的前提下，Index序列中下一个值Index[m+1]发生的事件为E2，概率为P(E2)，那么序列Index[1…m,m+1]是P(n,m+1)排列序列集合中的一个子序列的概率是：
P({E1}\cap{E2})
根据概率公式，上述等式等价于：
P({E1}\cap{E2})=P(E1)P(E2|E1)
P(E1)的值为：
\frac{(n-m)!}{n!}
P(E2|E1)的值为：
\frac{1}{(n-m)}
（从剩余的n-m个元素中随机挑选一个） 那么：
P({E1}\cap{E2})=P(E1)P(E2|E1)=\frac{(n-m)!}{n!}\frac{1}{(n-m)}=\frac{(n-(m+1))!}{n!}
因此，序列Index[1…m,m+1]是P(n,m+1)排列序列集合中的一个子序列的概率是：
\frac{(n-(m+1))!}{n!}
结束
当i=n，序列Index[1…n]是P(n,n)排列序列集合中的一个子序列的概率为：
\frac{(n-n)!}{n!}=\frac{1}{n!}
证明完毕。
解法2
求序列A[1…n]的随机排列的另外一个方法，逻辑相对简单。
伪代码
def premute_inplace(A):
for i = 1 to n:
swap(A[i], A[random(i,n)])
循环不变式
这个算法中的不变式：子序列A[1…i]为序列A的排列A(n,i)集合中的某个子序列的概率为：
\frac{(n-i)!}{n!}
证明方法与解法1类似。