objective-c - Objective-C中的加权随机字母

Question

我需要一种简单的方法来从字母表中随机选择一个字母，并根据我希望它出现的百分比加权。例如，我希望字母“E”在随机函数中出现 5.9% 的时间，但我只希望“Z”出现 0.3% 的时间（依此类推，基于每个函数的平均出现率）字母表中的字母）。有什么建议么？我看到的唯一方法是用 10000 个字母（590 个“E”、3 个“Z”等）填充一个数组，然后从该数组中随机选择一个字母，但这似乎是内存密集型和笨拙的。

Answer 1

不确定这是否可行，但似乎它可以解决问题：

1. 获取您的字母和频率列表，并将它们从最小频率排序到最大频率。
2. 创建一个 26 元素数组，其中每个元素 n 包含所有先前权重的总和以及频率列表中的元素 n。记下数组最后一个元素的总和
3. 生成一个介于 0 和您在上面记下的总和之间的随机数
4. 对总和数组进行二进制搜索，直到到达该数字将下降的元素

这有点难以理解，所以它会是这样的：

1. 如果你有一个 5 个字母的字母表，这些频率为 a = 5%、b = 20%、c = 10%、d = 40%、e = 25%，请按频率对它们进行排序：a、c、b、e、d
2. 保持元素的运行总和：5、15、35、60、100
3. 生成一个介于 0 到 100 之间的随机数。假设它是 22。
4. 对 22 下降的元素进行二分搜索。在这种情况下，它将位于元素 2 和 3 之间，即字母“b”（我认为，四舍五入是你想要的）

Answer 2

你已经承认空间和速度之间的权衡，所以我不会讨论这个。

如果您可以先验计算每个字母的频率，那么您可以预先生成一个数组（或动态创建并填充一次数组）以按您想要的精度级别进行扩展。

由于您使用了小数点后一位精度的百分比，因此请考虑一个包含 1000 个条目的数组。每个指数代表频率的十分之一。所以你必须等于letter[0]，等于letter[82]，依此类推，直到等于。（根据英文字母相对频率的值）'a'letter[83]letter[97]'b'letter[999]'z'

现在生成一个介于 0 和 1 之间的随机数（使用您拥有的任何喜欢的 PRNG，假设分布均匀）并将结果乘以 1000。这将为您提供数组的索引和加权随机字母。

Answer 3

使用此处说明的方法。唉，这适用于 Python，但可以为 C 等重写。 https://stackoverflow.com/a/4113400/129202

Answer 4

首先，您需要对字母及其频率进行 NSDicationary；

我会用一个例子来解释它：假设你的字典是这样的：

{@“a”：@0.2，@“b”，@0.5，@“c”：@0.3}；

所以你字母的频率以这种方式覆盖了 [0, 1] 的区间：

a->[0, 0.2] + b->[0.2, 0.7] + c->[0.7, 1]

您生成一个介于 0 和 1 之间的随机数。然后通过检查该随机数属于哪个区间并返回相应的字母，您可以轻松获得所需的内容。

您在程序开始时播种随机函数： srand48(time(0));

-(NSSting *)weightedRandomForDicLetters:(NSDictionary *)letterFreq {

double randomNumber = drand48();

double endOfInterval = 0;
for (NSString *letter in dic){
    endOfInterval += [[letterFreq objectForKey:letter] doubleValue];
    if (randomNumber < endOfInterval) {
        return letter;
    }
}

}