随机打乱加权数组

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）。对于为什么这种改组与这些权重不匹配，我有点模糊。有人可以解决我的困惑并告诉我如何解决吗？

以下是我找到的一些有用资源：

Random item by weight
Weighted Shuffle of an Array or Arrays?
How to implement a Weighted shuffle
One-line ruby weighted shuffle

Answer 1

这是一个很可能效率低下但希望足够有效的解决方案：（虽然我不保证正确性！而且代码不会让太多的 Rubyists 高兴...）。

算法的本质很简单，就是根据权重随机选取一个元素，将其移除，然后用剩余的元素重复。

def shuffle some_hash
   result = []

   numbers = some_hash.keys
   weights = some_hash.values
   total_weight = weights.reduce(:+)

   # choose numbers one by one
   until numbers.empty?
      # weight from total range of weights
      selection = rand() * total_weight

      # find which element this corresponds with
      i = 0
      while selection > 0
         selection -= weights[i]
         i += 1
      end
      i -= 1

      # add number to result and remove corresponding weight
      result << numbers[i]
      numbers.delete_at i
      total_weight -= weights.delete_at(i)
   end

   result
end

Answer 2

如果您将权重设为整数值，如下所示：

y = { 1 => 7, 2 => 2, 3 => 1 }

然后你可以构造一个数组，其中数组中每个项目的出现次数基于权重：

weighted_occurrences = y.flat_map { |id, weight| Array.new(weight, id) }
# => [1, 1, 1, 1, 1, 1, 1, 2, 2, 3]

然后进行加权洗牌就像：

weighted_occurrences.shuffle.uniq

经过 10,000 次洗牌并挑选出第一个 ID，我得到：

{
  1 => 6988,
  2 => 1934,
  3 => 1078
}

Answer 3

你给出了概率密度函数（P for "proability"）：

P(1) = 0.7
P(2) = 0.3
P(3) = 0.1

您需要构造（累积）分布函数，如下所示：

我们现在可以生成介于 0 和 1 之间的随机数，将它们绘制在 Y 轴上，向右画一条线以查看它们与分布函数相交的位置，然后读取相关的 X 坐标作为随机变量。所以如果随机数小于0.7，则随机变量为1；如果介于 0.7 和 0.9 之间，则随机变量为 2，如果概率超过 0.9，则随机变量为 3。（请注意，rand 等于 0.7（比如说）的概率几乎为零，因此我们不必为区分 < 0.7 和 <= 0.7 而感到遗憾。）

要实现它，首先计算散列 df:

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

last = 0.0
df = y.each_with_object({}) { |(v,p),h| last += p; h[last.round(10)] = v }
  #=> {0.7=>1, 0.9=>2, 1.0=>3}

现在我们可以创建一个随机变量如下：

def rv(df)
  rn = rand
  df.find { |p,_| rn < p }.last
end

让我们试试看：

def count(df,n)
  n.times.each_with_object(Hash.new(0)) { |_,count|
    count[rv(df)] += 1 }
end

n = 10_000
count(df,n)
  #=> {1=>6993, 2=>1960, 3=>1047} 
count(df,n)
  #=> {1=>6986, 2=>2042, 3=>972} 
count(df,n)
  #=> {1=>6970, 2=>2039, 3=>991}

请注意，键值对的顺序 count 由前几个随机变量的结果决定，因此键不一定按照它们在此处的顺序。

Answer 4

这是使用 Enumerable#max_by and this amazing result from Efraimidis and Spirakis 执行加权随机抽样的另一种方法：

给定一个散列，其值表示总和为 1 的概率，我们可以得到这样的加权随机抽样：

# hash of ids with their respective weights that sum to 1
y = { 1 => 0.7, 2 => 0.2, 3 => 0.1 }

# lambda that randomly returns a key from y in proportion to its weight
wrs = -> { y.max_by { |_, weight| rand ** (1.0/weight) }.first }

# test run to see if it works
10_000.times.each_with_object(Hash.new(0)) { |_, freq| freq[wrs.call] += 1 }

# => {1=>6963, 3=>979, 2=>2058}

附带一提，已经 talk 将加权随机抽样添加到 Array#sample，但该功能似乎在混乱中丢失了。

随机打乱加权数组

Randomly shuffle a weighted array

ruby

arrays

shuffle