从逆魏格斯地图中选择一个随机值

Question

我正在使用一张地图，其中包含我正在开发的刽子手游戏的合格单词。地图中的整数存储选择单词的时间，因此在开始时地图如下所示：

alabanza 0
esperanza 0
comunal 0
aprender 0
....

经过一些播放，地图将如下所示

alabanza 3
esperanza 4
comunal 3
aprender 1
....

我想随机选择下一个单词，但选择较少的单词被选中的概率更大。

我已经阅读了Java - 从哈希图中选择一个随机值，但分配了最高整数的值，但情况恰恰相反。

我还认为我可以使用带有重复单词的列表(单词在列表中出现的次数越多，选择的概率就越大(，但我只能做到这一点：

int numberOfWords=wordList.size(); //The Map
List<String> repeatedWords=new ArrayList<>();
for (Map.Entry<String,Integer> entry : wordList.entrySet()) {
for (int i = 0; i < numberOfWords-entry.getValue(); i++) {
repeatedWords.add(entry.getKey());
}
}
Collections.shuffle(repeatedWords);  //Should it be get(Random)?
String chosenWord=repeatedWords.get(0);

我认为当选择的单词数量等于单词数量时，这失败了。

编辑

最后，每个单词一旦具有不同的数字，它们的概率就会出现问题。我改变了观点，所以我首先输入一个概率 1000(它可以是任何数字(，每次我选择一个单词时，我都会将概率降低一定数量(假设为 20%(，所以我使用：

wordList.put(chosen,(int)(wordList.get(chosen)*0.8)+1);

之后，我选择Lajos Arpad或Ahmad Shahwan给出的食谱。 如果游戏要玩很多次，所有的概率都会趋向于1，但这不是我的情况。

感谢所有回答的人。

Answer 1

试试这个：

import java.util.Map;
import java.util.HashMap;
import java.util.Random;
public class MyClass {
public static void main(String args[]) {
Map<String, Integer> wordList = new HashMap<>();
wordList.put("alabanza", 3);
wordList.put("esperanza", 4);
wordList.put("comunal", 3);
wordList.put("aprender", 1);
Map<String, Integer> results = new HashMap<>(4);
for (int i = 0; i < 100; i++) {
String name = randomize(wordList);
Integer old = results.getOrDefault(name, 0);
results.put(name, old + 1);
}
for (Map.Entry<String, Integer> e : results.entrySet()) {
System.out.println(e.getKey() + "t" + e.getValue());
}
}
private static String randomize(Map<String, Integer> wordList) {
final Integer sum = wordList.values().stream().reduce(Integer::sum).orElse(0);
final int grandSum = (wordList.size() - 1) * sum;
final int random = new Random().nextInt(grandSum + 1);
int index = 0;
for (Map.Entry<String, Integer> e: wordList.entrySet()) {
index += (sum - e.getValue());
if (index >= random) {
return e.getKey();
}
}
return null;
}
}

输出是选择名称超过100次试验的次数：

aprender 37 alabanza 25 comunal 23 esperanza 15

您可以在这里自己尝试。

Answer 2

我不会提供确切的代码，但提供基本思想。

1. 遍历wordList.values()以查找最大权重M和权重总和S。

2. 现在让每个单词w都有可能(如概率，但它们的总和为 1(被选中M + 1 - wordList.get(w)，因此权重1的单词被选择的可能性是权重M的单词的M倍。

3. 可能性的总和将是(M + 1) * wordList.size() - S(这就是为什么我们需要S(。选择一个介于 0 和此总和之间的随机数R。

遍

4. 历wordList.entrySet()，边走边求和可能性。当总和通过R时，这就是你想要的词。

Answer 3

您的地图值就是您的权重。

您需要选择一个小于权重总和的整数。

选取每个字符串条目及其权重。当权重总和通过随机整数时，您将在字符串上。

这将为您提供：

public static void main(String ... args){
Map<String, Integer> wordList = new HashMap<>();
wordList.put("foo", 4);
wordList.put("foo2", 2);
wordList.put("foo3", 7);
System.out.println(randomWithWeight(wordList));
}
public static String randomWithWeight(Map<String, Integer> weightedWordList) {
int sum = weightedWordList.values().stream().collect(Collectors.summingInt(Integer::intValue));
int random = new Random().nextInt(sum);
int i = 0;
for (Map.Entry<String, Integer> e : weightedWordList.entrySet()){
i += e.getValue();
if (i > random){
return e.getKey();
}
}
return null;
}

Answer 4

为了简单起见，我们假设您有一个名为occurrences的数组，它包含int个元素(您可以轻松地将其转换为数据结构(。

现在，让我们找到最大值：

int max = 0;
for (int i = 0; i < occurrences.length; i++) {
if (max < occurrences[i]) max = occurrences[i];
}

让我们递增它：

max++;

现在，让我们为值为 0 的项目提供max

的权重，为发生过一次的项目提供max - 1的权重，依此类推(由于我们增加了max，因此没有项目的权重为 0(：

int totalWeight = 0;
for (int j = 0; j < occurrences.length; j++) {
totalWeight += max - occurrences[j];
}

请注意，所有物品都有其重量。现在，假设您有一个随机整数，称为r，其中0<= totalWeight：

int resultIndex = -1;
for (int k = 0; (resultIndex < 0) && k < occurrences.length; k++) {
if (r <= max - occurrences[k]) resultIndex = k;
else r -= max - occurrences[k];
}

结果是occurrences[resultIndex]