怎么写一个带概率的随机抽取模型？

[zhimingcc]

对于[1,2,3,4,5,6,7]这个数组，如果随机抽取，肯定每个数的被抽取的概率都是1/7,
代码大概是 Random.nextInt(7)就搞定了

如果人为增加一个概率，比如1，2概率是0.25，3，4，5，6，7都是0.1的概率，
该怎么写这样一个带概率的抽取模型？

[mengzhuo]

https://www.v2ex.com/t/142820#reply11

搭车同求更快的算法

[robbielj]

最简单的说可以抽两次吧
先分成[1,2]和剩下的，
第一次random两个组，都是0.5
第二次在组内random

[zhimingcc]

@robbielj 不能这么写死啊，我只是举个例子。。。。比如用不同的概率分布模型

[andyzhshg]

构造一个数组，里边1,2各25个，3,4,5,6,7各10个（不一定必须是25,10，可取最小整数倍，比如5和2），然后就继续用你说的算法就行了...不过我这办法看起来很矬的样子...

[CtrlSpace]

一个笨方法。
弄一个长数组，按比例存放要抽取的数据，然后随机抽取数组下标。

[staticor]

加一个权重的字典

[zhimingcc]

@mengzhuo GitHub被墙了。。。。先跪求翻墙软件，shadowsocksX感觉有点慢！

[guotie]

4楼的方法是最快的。

[lichao]

思路：

i = nextInt(1..100)

case i
when 1..25 then 1
when 26..50 then 2
when 51..60 then 3
when 61..70 then 4
when 71..80 then 5
when 81..90 then 6
when 91..100 then 7

[whywhy36]

sorry, no Chinese Input Method :-(

1. init one mapping according to the probability
1-25 -> 0
26-50 -> 1
51-60 -> 2
...
2. Random.nextInt(100)
3. pick the index from the mapping
4. get the number ...

[zhimingcc]

@lichao 赞一个！！简单但容易实现！！

[yxz00]

如果精度要求不是很高，四楼的方法不错

[khowarizmi]

发现跟楼上的思路重复了，但还是写一下吧.（仅仅针对lz给的例子）

p = Math.random()
if 0 < p < 0.25
x = 1
if 0.25 < p < 0.5
x = 2
....

[delphiqin]

我的方法
https://gist.github.com/37379f79fa03c3ff84d5.git

[delphiqin]

额，发代码失败，重来……
https://gist.github.com/DelphiQin/37379f79fa03c3ff84d5

[hahastudio]

其实这种带分布的随机选择挺多的啊= =
你能找到：
http://rosettacode.org/wiki/Probabilistic_choice#Python
https://stackoverflow.com/questions/526255/probability-distribution-in-python
http://glowingpython.blogspot.com/2012/09/weighted-random-choice.html

手写一个也没多费事= =
https://gist.github.com/hahastudio/b6bb65b6eccb11d154fb

[xiaoxiaoming]

可以用一个 类似 轮盘转法，命中率就是长度 或者是面积

[jokester]

Weighted random sampling with a reservoir 这篇论文给出了一个保证one-pass的算法

[feiyuanqiu]

php：

function rand_weight($numbers)
{
$total = 0;
$dist = array();
foreach ($numbers as $num => $weight) {
$total += $weight;
$dist[$num] = $total;
}
$rand = mt_rand(0, $total - 1);
foreach ($dist as $num => $weights) {
if ($rand < $weights) { return $num; }
}
}

[feiyuanqiu]

使用：
$a = array(
'this' => 10, // 50%
'is' => 2, // 10%
'a' => 5, // 25%
'test' => 3, // 15%
);
$result = array();
for ($i=0; $i < 100; $i++) {
$result[] = rand_weight($a);
}
print_r(array_count_values($result));exit;

// 结果： Array ( [a] => 24 [this] => 50 [is] => 8 [test] => 18 )

[jokester]

@jokester 补充. 那个论文是n中抽m(m<=n)的方法. n中抽1不用那么复杂.

[zoowii]

生成一个[0, 1)的小数,然后按权重分配这段长为1的线段.然后看这个随机生成的小数在哪个区间即可

[bingwenshi]

刚好前几天研究过类似的问题, 楼主可以看下我的这篇博客

http://segmentfault.com/blog/shibingwen/1190000000735405

[bingwenshi]

方法不一定比楼上各位的好, 但是思路会比较清晰点

[lygmqkl]

@lichao 这个方法好，不局限在目标array，跳出来构建一个概率数组，然后根据概率数组获得的值直接取整对应到目标array

[walleL]

圆桌算法 代码参考 @feiyuanqiu 的
游戏里面经常用到

[xiaowangge]

游戏开发用到的是，填写成配置文件。

[yangzh]

已知了概率分布的概率累积函数 F(x)，也可以从均匀分布 U[0,1] 中随机取 u ，再求 x=F^(-1)(u) ，x 即是想要随机样本。

此为统计学上的标准答案。建议楼主找个周围学过概率学的朋友问问。