【洗牌算法】在n个数中等概率取m个数 逻辑

mac2024-10-04  52

【洗牌算法】在n个数中等概率取m个数 逻辑

Shuffle算法

很巧

数组:【 x1 x2 x3 …… xi …… xn 】,在 n(1-n)个数(不相同)中等概率取m个数 逻辑: 样本是n,取某个数,这个数放在第i个位置,确保前面i-1个没有中,第i个中了 从第一个位置开始 没有中的概率是(1-1/n) 直到第i-1个没有中的概率 (1-1/(n-i+2)) ,而第i个数中了就是1/(n-i+1) 然后取的话就是从1-m个位置取随机(1-n)

Knuth 算法

相对来说逻辑一样只是把 开辟出来的结果数组 换到了数组的最后,每次取到了就交换到最后,节省了遍历时间和空间

最近在看:抽奖正反保底 参考:https://blog.csdn.net/qq_25026989/article/details/89512769

最新回复(0)