ruby - 选择一个随机选项，其中每个选项被选中的概率不同

Question

假设给您三个“选项”，A、B 和C。

您的算法必须随机选择并返回一个。为此，只需将它们放在一个数组 {A,B,C} 中并生成一个随机数(0、1 或 2)，这将是元素在返回数组。

现在，这个算法有一个变体:假设 A 有 40% 的机会被选中，B 有 20%，而 C 40%。如果是这种情况，您可以采用类似的方法:生成一个数组 {A,A,B,C,C} 并生成一个随机数 (0, 1, 2, 3, 4)选择要返回的元素。

行得通。但是，我觉得效率很低。想象一下，将此算法用于大量 选项。你会创建一个有点大的数组，可能有 100 个元素，每个元素代表 1%。现在，这仍然不是很大，但假设您的算法每秒使用多次，这可能会很麻烦。

---

我考虑过创建一个名为 Slot 的类，它有两个属性:.value 和 .size。为每个选项创建一个插槽，其中 .value 属性是选项的值，而 .size 相当于该选项的出现次数在数组中。然后生成一个从0到总出现次数的随机数，看看这个数落在了哪个slot上。

我更关心算法，但这是我的 Ruby 尝试:

class Slot
  attr_accessor :value
  attr_accessor :size
  def initialize(value,size)
    @value = value
    @size  = size
  end
end

def picker(options)
  slots = []
  totalSize = 0
  options.each do |value,size|
    slots << Slot.new(value,size)
    totalSize += size
  end
  pick = rand(totalSize)
  currentStack = 0
  slots.each do |slot|
    if (pick <= currentStack + slot.size)
      return slot.value
    else
      currentStack += slot.size
    end
  end
  return nil
end

50.times do
  print picker({"A" => 40, "B" => 20, "C" => 40})
end

哪些输出:

CCCCACCCCAAACABAAACACACCCAABACABABACBAAACACCBACAAB

---

是否有更有效的方法来实现选择随机选项的算法，其中每个选项都有不同的被选中概率？

Answer 1

最简单的方法可能是写一个case语句:

def get_random()
  case rand(100) + 1
    when  1..50   then 'A'
    when 50..75   then 'B'
    when 75..100  then 'C'
  end
end

问题是你不能传递任何选项，所以如果你想让它能够接受选项，你可以写一个这样的函数。下面的那个与您写的非常相似，但更短一些:

def picker(options)
  current, max = 0, options.values.inject(:+)
  random_value = rand(max) + 1
  options.each do |key,val|
     current += val
     return key if random_value <= current
  end
end

# A with 25% prob, B with 75%.
50.times do
  print picker({"A" => 1, "B" => 3})
end
# => BBBBBBBBBABBABABBBBBBBBABBBBABBBBBABBBBBBABBBBBBBA

# If you add upp to 100, the number represent percentage.
50.times do
  print picker({"A" => 40, "T" => 30, "C" => 20, "G" => 10})
end
# => GAAAATATTGTACCTCAATCCAGATACCTTAAGACCATTAAATCTTTACT