随机打乱加权数组

Question

有一个包含 ID 和这些 ID 的权重的哈希值。

y = { 1 => 0.7, 2 => 0.2, 3 => 0.1 }

我想根据权重对这个哈希值进行洗牌。

我尝试了多种不同的方法，所有这些都给我带来了相似的、意想不到的结果。这是我发现的最简洁的。

y.sort_by {|v| -v[1]*rand()}

当我运行此一万次并选出第一个 ID 时，我得到以下计数：

{1=>8444, 2=>1316, 3=>240}

我希望这些计数能够反映上面的权重（例如1=> 7000）。我有点不清楚为什么这种洗牌与这些权重不匹配。有人可以消除我的困惑并告诉我如何解决它吗？

以下是我发现的一些有用的来源：

• 按重量随机物品
• 一个或多个数组的加权洗牌？
• 如何实现加权洗牌
• 单行 ruby​​ 加权随机播放

Answer 1

这是执行加权随机抽样的另一种方法，使用Efraimidis 和 SpirakisEnumerable#max_by得出的惊人结果：

\n\n

给定一个哈希值，其值代表总和为 1 的概率，我们可以得到如下的加权随机采样：

\n\n

# hash of ids with their respective weights that sum to 1\ny = { 1 => 0.7, 2 => 0.2, 3 => 0.1 }\n\n# lambda that randomly returns a key from y in proportion to its weight\nwrs = -> { y.max_by { |_, weight| rand ** (1.0/weight) }.first }\n\n# test run to see if it works\n10_000.times.each_with_object(Hash.new(0)) { |_, freq| freq[wrs.call] += 1 }\n\n# => {1=>6963, 3=>979, 2=>2058}\n

\n\n

顺便说一句，有人讨论过向中添加加权随机采样Array#sample，但该功能似乎在混乱中消失了。

\n\n

进一步阅读：

\n\n

\n
1. Enumerable#max_by\xe2\x80\x94的Ruby-Docwsample特别是示例
\n
2. Efraimidis 和 Spirakis (2005) 的加权随机采样引入了该算法
\n
3. Array#sample、Array#choice 的新功能提到了添加加权随机采样的意图Array#sample
\n

\n