java - 选择一个随机加权元素，有样本，无替换

Question

给定一个表示战利品表中奖励的结构，其中 a 是奖励类型，2 是整数权重，这意味着 a 被取出的可能性是 d 的两倍。

Map{
  "a" -> 2
  "b" -> 2
  "c" -> 2
  "d" -> 1
  "e" -> 1
  "f" -> 1
}

如何生成用于展示目的的示例 + 获胜者？

我当前的(伪)代码:

list out;
foreach(entry:map){
  for(entry.value){
    out.add(a)
  }
}

然后创建一个用于显示的示例。

Collections.shuffle(out);
List display = out.stream()
  .distinct()
  .limit(8)
  .collect(Collectors.toList());

使用此代码，如果我通过

选择获胜者，我可以相信 .distinct 不会扭曲赔率吗？

winner = display.get(0);

我意识到添加最后一个元素可能会扭曲结果，因为在发生不同的调用之后，它更有可能选择权重较低的数字。

但是选择流的第一个元素应该是值得信赖的，对吧？因为它是在 .distinct 之前选择的，所以它具有状态诱导效果？

Answer 1

看看Stochastic universal sampling和 Fitness proportionate selection 。根据权重抽取一个样本的简单方法可以通过将每个元素表示为一个长度与其权重成比例的区间来解释。例如:

Map{
  "a" -> 2 // weight 2
  "b" -> 2
  "c" -> 2
  "d" -> 1
  "e" -> 1
  "f" -> 1
}
=>
Map{
  "a" -> (0,2) // weight 2 -- is now length of the interval
  "b" -> (2,4) // ...
  "c" -> (4,6)
  "d" -> (6,7)
  "e" -> (7,8)
  "f" -> (8,9)
}

然后你选择从 0 到 9 的随机数 9*Math.random() (作为指向范围的指针)并检查它属于哪个区间 - 这是你的随机样本输入权重。重复直到获得所需数量的样本(如果您愿意，可以忽略重复项)...

当然，这是一个有点惯用的解释，在真正的代码中，您将只保留上限，因为下限只是前一个元素的上限。然后您将选择边界位于随机指针上方的第一个元素。

<小时/>

更新:从数学角度来看，重复元素的原始方法是可以的(选择具有双倍权重的 elament 的概率是双倍)，但当权重较高时，这将是一个问题:Map{"a”->1000 “b”->100000}。而且它也不能很好地处理实值权重。