用随机魔法解决场景问题

抛出问题

1.已知规模的数值,如何随机划分给n个元素,不得分配0

2.随机生成一个排列

3.带有权重的随机,不同的元素有不同的概率(总和100%),从中挑1个

4.未知规模的流,从中随机挑k个元素

5.搞个随机数生成器

Solve 1

不得为0的话我们就首先全部分配一个最小单位,相当于把这个条件去掉再讨论

微信红包的做法

  1. 如果划分规模只有1,直接返回

  2. 否则范围在[0,剩余平均值的2倍]中随机挑,规模减一

官方QA:你这样能真的随机吗? 不知道,我从没想过这个问题

(当年面试反问的时候,面试官说:我们也没什么特别好的方法。。)

Solve 2

方法挺多的,挑个最顺眼的

knuth shuffle

for(int i = arr.size()-1; i; --i) {
    swap(arr[i],arr[rand()%(i+1)]);
}

(相当于每次不放回地从口袋挑出一个球,挑出来的就是swap后的arr[i])

对于第$1$次筛选,任意一个被选中的概率是$1/n$

对于第$2$次筛选,剩余被选中的概率是$\frac{n-1}{n} \cdot \frac{1}{n-1}=\frac{1}{n}$

对于第$3$次筛选,剩余被选中的概率是$\frac{n-1}{n} \cdot \frac{n-2}{n-1} \cdot \frac{1}{n-2} =\frac{1}{n}$

归纳到第$k$次同理

Solve 3

其实这是氪金抽卡问题!

从100%入手

抽卡的最终概率和为100%,可构造(预处理)一个总和为100长度为种类数量的数组,然后rand加上二分即可,这种简单的方法花费$O(logn)$

从标记入手

能不能$O(1)$?那就构造个完整的长为100的数组,每个元素标记属于哪个即可,但要是精度高一点,比如0.0000001%,那空间就太浪费了

别名算法

alias method可以实现$O(1)$时间以及$O(n)$空间

大概意思是,首先分$n$个元素的数组,对应于其概率

然后每个元素均乘上$\frac{1}{P}$,$P$是平均概率

每个元素的值可能大于小于或者等于$P$

我们逐步把大于$P$的部分完整填充到小于$P$的剩余部分,

这样每个元素就可能是表示复合的状态,但每个元素的总值均为$P$

与处理完后只需抛出两次rand,第一次是rand(0,n-1),表示要扔到第几个元素,第二次是rand(0,P),表示要选定哪一边才是真正选择的对象

Solve 4

蓄水池算法适用于对一个未知规模的数据集进行采样

蓄水池算法

假设最终要挑出$k$个,我们要构造一个大小为$k$的数组

流中的前$k$个数据依次塞入数组

从$k+1$开始,以$\frac{k}{k+1},\frac{k}{k+2}\cdots$的概率选择该对象并随机替换,一直往复

直到最后得知流规模为$n$,最终每个对象被选中的概率为$\frac{k}{n}$

第$i$个元素被选中的概率为(选择$i$的概率)×(后面各元素不被选择的概率+后面被选择×不被替代第$i$的概率)

$P = \frac{k}{i} \prod_{j=i+1}^{n}(\frac{j-k}{j}+\frac{k}{j} \cdot \frac{k-1}{k}) = \frac{k}{i} \prod_j \frac{j-1}{j} = \frac{k}{n}$

Solve 5

首先拿当前时间戳作为随机数哈希映射的全部打死,想象一下同一ms内随机数全部相同的恐惧

实用方向的话,目前找到的较为方便的实现有

  1. 各语言都提供的线性同余法,就是SEED=(SEED*a+b)%M的形式,参数挑大素数基本都挺稳的
  2. 周期非常长的xor-shift,据说JDK也用它来生成默认的hashCode

限于个人姿势水平,不提供随机证明了

发表评论

电子邮件地址不会被公开。 必填项已用*标注