关于随机数
随机数是一个很神奇的东西, 基于随机数衍生出来很多有意思的算法
洗牌算法
得到一个M以内的所有自然数的随机顺序数组
洗牌之后, 如果能够保证每一个数出现在所有位置上的概率是相等的, 那么这种算法是符合要求的
当然, 最直观的想法就是随机一个数, 如果已经取过, 则重新抽取, 否则加入数组
1
这个思路有两种实现方式:
1.1
每次随机 [0,M-1] 得到一个数
如果该位置不为-1, 则取出并置位-1;
否则重抽
这种算法会导致多次抽到相同的数字, 开销很大
1.2
每次随机 [0,M-1] 得到一个数
将该数取出, 并删除, M–
相比于法1, 每次随机一定会得到一个结果, 但是删除的开销也很大
2
换一个思路
每次随机选两张牌, 交换他们, 随机一定的次数, 得到结果
如何确定这个次数来保证绝对公平? 我还没学会
3
Knuth-Shuffle 发明了洗牌算法
众所周知, 经典的算法都是简易而高效的
将最后一个数和前面任意 n-1 个数中的一个数进行交换（也可以不换），然后倒数第二个数和前面任意 n-2 个数中的一个数进行交换，如此往复直到最后一个元素
1 | |
算法不需要开辟额外空间, 时间复杂度为 $o(n)$ 相当完美!
下面来简单论证一下这个算法的正确性
需要证明洗牌算法的正确性, 需要论证两点
- 一张牌出现在每个位置的概率是相等的
2.一个位置出现牌的概率是相等的
先来证明1
对于第一张牌, 他出现在最后一个位置的概率为 $1/n$ (第一轮抽到1号牌的概率)
出现在倒数第二个位置的概率为 $(n-1)/n * 1/(n-1) = 1/n$ (第一轮没抽到1号牌且第二轮抽到1号牌)
…
接下来证明2
对于最后一个位置, 装1的概率为 $1/n$
装2的概率为$(n-1)/n * 1/(n-1) = 1/n$
…
好耶
4
但是这种算法也有一定的局限性
最明显的就是原数组顺序被打乱了
当然, 要解决这个问题, 只需要另外开辟一个空间做个拷贝即可
接下来是一个不可避免的问题: 假设我们不知道M的大小, 换一句话说, M是一个动态增长(只有增)的数字呢?
Inside-Out Algorithm解决了这一问题
从前向后扫描数据, 把位置 i 的数据随机插入到前 i 个 (包括第 i 个) 位置 (假设为k)
然后把原始数据中位置 k 的数字替换新数组位置 i 的数字, 其实效果相当于新数组中位置 k 和位置 i 的数字进行交换
蓄水池抽样算法
我更喜欢叫它抽牌算法
从n个数据中随机取得m个数，n>m
从前往后遍历数组, 当 i < m 时, 放入新数组
当 i >= m 时, 随机[0, m), 设为k, 若 k < m, 则将新数组中的 k 替换
随机数的映射
简单的说, 就是给一个随机数, 要求设计某种变换得到另一个随机数
假设randx可以生成 [1,x] 的随机数
从大范围rand中得到小范围
这个很简单, 因为我们平时就会用, mod一下就行
注意丢弃掉最后一部分数
eg:
rand18 -> rand5
如果随机出来的是17或18, 则丢弃
否则 (rand18)%4 + 1
从小范围rand中得到大范围
这种情况稍微复杂一点
那么我们先来考虑一种简单的情况
现有随机数rand可以随机 [0, 9]
实现0~99的随机函数
很简单, 分为个, 十 两位数, 分别随机后即为答案
那么, 考虑生成
0~150之间的随机数呢
当然我们可以生成0~999间的随机数,然后利用1中的方法得到答案
接下来回到问题
其实我们上述已经解决了10进制下的问题
那么, 解决n进制下的问题也是一样的思路