字典單詞的隨機選擇

我想從數組中選擇一定數量的隨機單詞，使總數爲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 Arnas

請注意，使用模數來限制隨機數的間隔會產生偏差。 – 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:21:27

添加隨機數字會改變分佈。 – 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

你應該得到一個新的隨機數而不是增加索引。你這樣做的方式，所有不符合你的標準的字符串「吸引」更多的隨機數字，並可能導致下面的字符串被選擇的概率更高。

來源

2012-03-04 13:02:16 PlasmaHH

似乎沒有幫助，而調試數字似乎是隨機的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()大多數實現是相當簡單的，不得提供一個良好的正態分佈開始。

來源

2012-03-04 16:25:54

字典單詞的隨機選擇

回答

相關問題