字典单词的随机选择

问题描述：

我想从数组中选择一定数量的随机单词，使总数为36个字母。字典单词的随机选择

起初我试图选择一个随机单词，并在检查它不超过我们拥有的可用空间量之后添加它。这样做效率不高，因为名单会被填满，只剩下2-3个字母的空白空间，需要很长时间才能找到这样一个简短的单词。

所以我决定只选择六个6个字母的单词，我通过生成一个随机数然后递增1直到找到一个6个字母的单词。这很快，但是这些单词并不是随机的，通常我会得到从同一个字母开始的单词，或者只有以a，b，c或x，y，z等序列开头的单词。

srand (time(NULL)); 
for(int i=0;i<6;i++) 
{ 
    randNumb = rand()%dictionary.size(); 
    while(dictionary.at(randNumb).length() != 6) 
    { 
     randNumb++; 
    } 
    a << "/" << dictionary.at(randNumb) << "/"; 
}

我想选择不同长度，但赞成的表现，我会只用6个字母的单词解决的话，但随后它们更随机选择我至少希望。

请注意，使用模数来限制随机数的间隔会产生偏差。 – 2012-03-04 13:27:08

答

rand() function生成0和RAND_MAX之间的数字。

如果RAND_MAX定义为32767，那么您不会访问字典（数组？）中索引大于该数组的元素。

如果你需要产生比RAND_MAX更大的随机数，再想想求和的rand()n调用，这样n * RAND_MAX >= dictionary.size()结果。然后保证这个结果的模数给出一个落在整个字典范围内的索引。

添加随机数字会改变分布。 – 2012-03-04 13:25:13

均匀分布总和的分布是正态分布，这是真的。但是真正的问题在于生成的索引是在[0，RAND_MAX]而不是[0，dictionary.size（） - 1]的范围内，因此并非所有的字典元素都可以访问。所以，不管用什么方法生成随机数，输出允许访问整个字典似乎很重要。 – 2012-03-04 13:32:37

那么解决了一切。 – Arnas 2012-03-04 13:32:46

答

你应该得到一个新的随机数而不是增加索引。你这样做的方式，所有不符合你的标准的字符串“吸引”更多的随机数字，并可能导致下面的字符串被选择的概率更高。

似乎没有帮助，而调试数字似乎是随机的0-40,000范围内，但字典有250,000字。我猜这是因为新的随机数之间的间隔很短。 – Arnas 2012-03-04 13:11:06

@Arnas：你不说什么让你觉得它“不起作用”。当你的字典本质上是非随机的时候（这很可能只有25万字），那么当然字串也是非常随意的。 – PlasmaHH 2012-03-04 13:25:46

答

即使RAND_MAX大于dictionary.size()，使用%算子选择索引导致非均匀分布。模数将导致早期单词比后面单词更频繁地选择（除非RAND_MAX + 1是dictionary.size()的整数倍）。

考虑一个简单的例子：假设你的字典有10个字，而RAND_MAX是14.当rand()返回一个从0到9的值时，直接选择相应的字。但是当rand()是10到14时，将选择前五个单词中的一个。所以前五个单词的选择机会比最后五个单词的两倍。

一种更好的方式来映射[0 .. RAND_MAX]到[0 .. dictionary.size()）是使用划分：

assert(RAND_MAX + 1 >= dictionary.size()); 
randNumb = rand() * dictionary.size()/(RAND_MAX + 1);

但是你必须要小心整数溢出的。如果RAND_MAX * dictionary.size()大于您可以用整数表示，则需要使用更大的数据类型。为了这个目的，一些系统具有如MulDiv的功能。如果你没有像MulDiv，你可以转换为浮点类型，然后截断结果返回一个整数：

double temp = static_cast<double>(rand()) * dictionary.size()/(RAND_MAX + 1); 
randNumb = static_cast<int>(temp);

这是仍然一个不完美的分布，但“热”字现在将在字典中均匀分布，而不是在开始阶段聚集。

RAND_MAX + 1越接近dictionary.size()的整数倍越好。如果您不能确定它接近整数倍，那么您希望RAND_MAX相对于dictionary.size()尽可能大。

既然您对RAND_MAX没有太多的控制权，您可以考虑调整dictionary.size()。例如，如果你只需要六个字母的单词，那么为什么不把所有其他单词从字典中删除呢？

std::vector<std::string> six_letter_words; 
std::copy_if(dictionary.begin(), dictionary.end(), 
      std::back_inserter(six_letter_words), 
      [](const std::string &word){ return word.size() == 6; });

随着减少集，我们可以用一个更通用的算法来选择的话：

typedef std::vector<std::string> WordList; 

// Returns true with the given probability, which should be 0.0 to 1.0. 
bool Probably(double probability) { 
    return (static_cast<double>(std::rand())/RAND_MAX) < probability; 
} 

// Selects n words from the dictionary using a normal distribution and 
// copies them to target. 
template <typename OutputIt> 
OutputIt Select(int n, const WordList &dictionary, OutputIt target) { 
    double count = static_cast<double>(n); 
    for (std::size_t i = 0; count > 0.0 && i < dictionary.size(); ++i) { 
     if (Probably(count/(dictionary.size() - i))) { 
      *target++ = dictionary[i]; 
      count -= 1.0; 
     } 
    } 
    return target; 
}

的想法是通过每个字在字典中的步骤，并与的概率选择它您需要选择的字数除以剩下的字数。这很好，即使RAND_MAX比较小。总的来说，它比计算随机选择索引要多得多。还要注意，这种技术不会多次选择同一个词，索引映射技术可以。

你叫Select这样的：

// Select six words from six_letter_words using a normal distribution. 
WordList selected; 
Select(6, six_letter_words, std::back_inserter(selected));

还要指出的是rand()大多数实现是相当简单的，不得提供一个良好的正态分布开始。

字典单词的随机选择

相关推荐