flutter - 生成加权随机字母列表

Question

我正在尝试创建一个文字游戏，并希望向用户呈现字母，以便他们构建单词。鉴于此，我有一个名为 lettersList 的可用字母源列表，目前只有英文字母表中的 26 个字母。

对于用户来说，我只希望他们用 5 个字母来构建一个单词。为了生成 5 个字母的列表，我有以下内容:

  var randomList = new List.generate(5, (_) => lettersList[Random().nextInt(lettersList.length)]).toList();

这种方法可行，因为我不介意重复，但我希望某些字母比其他字母出现得更多，例如元音和最常见的辅音。

因此，我能想到的唯一解决方案是扩充我的 lettersList 以添加更多我想更频繁地显示的字符(例如，对于字母 E，也许我会添加 5 个字符)在 letterList 中添加更多实例或添加 3 个字母 N 的实例)并更改我的代码以使用随机播放。

  lettersList.shuffle();
  return lettersList.take(5).toList();

所以，即使这有效，我只是很好奇，是否有更好或更有效的方法来做到这一点？

Answer 1

您建议的方式(使用某些字母的倍数)本身并不是一个坏主意，但没有太多灵活性。

您真正想要做的是为每个字母设置一组加权值，然后在它们之间进行选择。

一种简单的方法是定义字母表中每个字母的权重，即

{ 'a': 1, "b": 0.8, "c": 1.2 ... }

然后，要获得随机分布，您可以使用 random.nextDouble() * <sum of all the weights> 。这将产生一个介于 0 和总和之间的数字 - 您所需要做的就是找出对应于哪个位置。您可以从 0 开始，检查添加到总和中的每个数字的权重是否大于随机双倍数。

然后您可以将其包装在一个类中，可能会对默认值进行一些初始化。您可以check it out on dartpad但我也将其包含在下面。

此类以通用方式处理随机分布:

import 'dart:math';
import 'package:collection/collection.dart';
class WeightedRandom<T> {
  WeightedRandom(Map<T, double> allWeights)
      : _totalWeight = allWeights.values.sum,
        _allWeightsList = allWeights.entries.toList(growable: false);

  final double _totalWeight;
  final Random _random = Random.secure();
  final List<MapEntry<T, double>> _allWeightsList;

  T getNext() {
    final weightedRandom = _random.nextDouble() * _totalWeight;
    double totalSoFar = 0;
    for (final entry in _allWeightsList) {
      if (weightedRandom < totalSoFar + entry.value) {
        return entry.key;
      }
      totalSoFar += entry.value;
    }
    return _allWeightsList.last.key;
  }
}

这个使其特定于字母，并具有设置默认值的额外好处:

class RandomWeightedLetter extends WeightedRandom<String> {
    static final _defaultWeights = Map.fromEntries(
      List.generate(26, (ind) => MapEntry(String.fromCharCode(ind + 97), 1.0)));
  
  RandomWeightedLetter._(Map<String, double> allWeights): super(allWeights);
  
  factory RandomWeightedLetter(Map<String, double> specialWeights) {
    for (final entry in specialWeights.entries) {
      assert(entry.key.length == 1 &&
          entry.key.codeUnits.first >= 97 &&
          entry.key.codeUnits.first <= 122);
    }
    final allWeights = _defaultWeights..addAll(specialWeights);
    return RandomWeightedLetter._(allWeights);
  }
}

您可以通过非常简单的方式使用它，即:

void main() {
  final random = RandomWeightedLetter({'f': 26});

  final counts = Map.fromEntries(
      List.generate(26, (ind) => MapEntry(String.fromCharCode(ind + 97), 0)));

  const rounds = 100000;
  for (int i = 0; i < rounds; ++i) {
    final randomLetter = random.getNext();
    counts[randomLetter] = counts[randomLetter]! + 1;
  }
  print(counts.map((key, value) => MapEntry(key, value / (rounds / random._totalWeight))));
}

(打印出类似这样的内容，表明分发有效):

{a: 0.95421, b: 0.99144, c: 0.9894000000000001, d: 0.98634, e: 0.99297, f: 26.18646, g: 0.9679800000000001, h: 1.03479, i: 0.9741, j: 0.9945, k: 1.02408, l: 0.9639, m: 0.98481, n: 0.9537, o: 1.0098, p: 0.99093, q: 1.00827, r: 0.97971, s: 1.0251000000000001, t: 1.02204, u: 0.97104, v: 1.01286, w: 0.98634, x: 0.94911, y: 1.04142, z: 1.0047}

然后，为了达到您想要的效果，您可以简单地这样做:

final random = RandomWeightedLetter(...);
final randomList = List.generate((_) => random.next());

请注意，这并不是特别优化的 - 您可以预先计算“桶”并执行一些更奇特的算法，而不仅仅是每次迭代以从随机 double 到字母，但这对于相当小的一组潜在值。如果你想要有大量的潜在值，你会想做一些更聪明的事情 - 一种简单的方法是计算每个潜在响应的最大值，然后使用平衡树之类的东西来“排序”新值放入其中。