随机算法和C代码实现总结

terry 2年前 (2023-09-27) 阅读数 66 #数据结构与算法

随机算法涉及大量概率论。有时很难仔细观察推导过程。当然，充分理解推导过程是很有用的。如果你不明白推导过程，至少记住它。还需要一个结论。这篇文章总结了我几年前找工作时写的一些最常见的随机算法问题。需要注意的是，随机函数randInt(a, b)随机生成[a,b]范围内的整数，即生成每个整数。是相等的（虽然这在实践中可能是不可能的，但是不要太在意，这个世界上的很多事情都是非常随机的）。本文的代码在这里。

1 随机排列数组

假设一个数组A 包含元素 1 到 N，目标是生成该数组的均匀随机排列。

一种常见的方法是为数组 A[i] 的每个元素分配随机优先级 P[i]，然后按优先级对数组进行排序。例如，我们的数组是 A = {1, 2, 3, 4}。如果选择的优先级数组是 P = {36, 3, 97, 19}，我们得到序列 B={2, 4, 1, 3}，有最高优先级 (97) 和 2 具有最低优先级 (3)。该算法必须生成一个优先级数组，并使用它对原始数组进行排序。这里不再详细描述。有一种更好的方法来获取随机排序的数组。

生成随机排列数组的更好方法是就地排列（就地）。给定一个数组，这可以在 O(N) 时间内完成。伪代码如下：

RANDOMIZE-IN-PLACE ( A , n ) 
	for i ←1 to n do 
		swap A[i] ↔ A[RANDOM(i , n )]
复制代码

如代码所示，迭代i从元素A中产生元素A[i]♺...n]随机选择从开始，迭代i之后，我们永远不会改变A[i]。

A[i] 位于任意位置 j 的概率为 1/n。很容易推导出来。例如，A[1] 位于位置 1 的概率为 1/n。这是显而易见的，因为 A[1] 不是将元素从 1 替换为 n 的概率是 1/n，然后它不会改变

。并且 A[1] 位于位置 2 的概率也是 1/n，因为如果

A[1]A[1]❀ 它必须首先时间位于位置 2。替换 A[k] (k=2...n)，同时将第二个 A[2] 替换为  A[k] 第二次，没有。一种替换 A[k] 的概率为 (n-1)/n，另一种替换的概率为 1/(n-1)  ，所以总概率为 (n-1)/n * 1/(n-1) = 1/n。对于其他情况也可以推导出同样的原理。  当然，这个条件只能是数组随机排序的必要条件。这意味着元素 A[i] 位于位置 j 的概率为 1/ n，它可能不会给出随机含义。有序数组。由于它产生的排列数小于n！，即使概率相等，排列数也达不到要求。算法导论里就有这样一个反例。 
算法随机性可以生成均匀的随机排列。其证明过程如下： 
首先给出k放置的概念。所谓k排列就是从n个元素中选择k个元素。元素的排列，那么总共有 n!/(n-k)! k 种排列。 
单一性不变量：在 for 循环第 i 次迭代之前，对于每种可能的排列 i-1，子带 A[1...i-1] 包含排列 i-1 的概率为  ( n-i+1)! / n！。 
初始化：在第一次迭代i=1之前，那么循环不变式意味着对于每0个排列，子游A[1...i-1]包含0个排列的概率为(n -1+1)! /n！ = 1。 A[1...0] 是一个空数组，0 排列中没有元素，因此 A 包含所有可能的 0 排列的概率为 1。不变量成立。 
维护：假设第i次迭代前，数组的排列i-1出现A[1...i-1]的概率为 i+1） !/ n!，则第 i 次迭代后，数组 i 的所有排列出现在 A[1...i] 中的概率为 ( n-i)！ /n！ 
。我们得出以下结论： 
考虑一个特殊排列 p = {x1, x2, ... xi，由 p-1 排列 p = {x 组成, x2, ... x2,..., xi−1 } 后面跟着 xi。定义两个事件变量E1和E2：
E1是算法组织p'到A[1...i-1]的事件。概率如下。发现归纳假设为Pr(E1) = (n-i+1)！ / n！。 
E2 是将 xi 放入第 i 次迭代A[i] 的事件。因此，我们得到排列 i 发生在 A[1...i] 中的概率为 Pr {E2 ∩ E1} = Pr {E2 | E1} {E1}女士。和 Pr {E2 | E1} = 1/(n − i + 1)，因此 Pr {E2 ∩ E1} = Pr {E2 | E1} Pr {E1}= 1 /(n − i + 1) * (n − i + 1)! /n！ = (n − i )! / n！。 
结束：如果结束，i=n+1，这样我们就得到A[1...n]，给定n的排列。概率为 1 /n！ 。 
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!=6。为了使这些排列出现的概率等于 1/6，每个排列 m 的出现次数必须对应于 m/27=1/6。显然，不存在满足条件的整数。事实上，每种排列出现的概率如下，例如{1,2,3}为4/27，不等于1/6 。排列 概率
4/27
5/27 5/271  5 /27 /27。 4/27
2 随机选择一个数字 
 问题： 给定未知长度的整数流，如何随机选择一个数字？ （所谓随机，就是每个数字被选中的机会均等） 
方案一： 如果数据流不是很长，可以先存入数组，然后从数组中随机选择。当然，问题是关于未知的长度，因此如果长度太大而无法存储在内存中，则该解决方案有其局限性。 
解决方案2：  如果数据流很长，可以这样做： 
如果数据流在第一个数字之后结束，则必须选择第一个数字。 
如果数据流在第二个数字之后结束，那么我们选择第二个数字的概率是1/2。我们以 1/2 的概率用另一个数字替换之前选择的随机数，得到一个新的随机数。随机数。 
......
如果数据流在第n个数字之后结束，那么我们选择第n个数字的概率是1/n，也就是说我们以1/n的概率使用第n个数字进行替换先前选择的随机数以获得新的随机数。 
使用随机函数f(n)=bigrand()%n很容易，其中bigrand()返回非常大数据的随机流的第一个如果n，如果f(n)==0，则替换之前选择的随机数，这样保证选择每个数字的概率为❀ 1/n

排列	概率
	4/27
	5/27	5/271 5 /27 /27。 4/27

。例如，如果n=1，则f(1)=0，则选择数字1，如果

n=2，则选择数字的概率是 1 /2。类似地，如果数字的长度为n，则选择第n个数字的概率为1/n。代码如下（注：在Linux/MacOS上，函数rand()已经可以返回一个很大的随机数，所以用bigran()）：

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);
}
复制代码