選擇長度最多爲n的均勻隨機字符串？

Question

假設我想從長度至多爲n的所有字符串中選擇一致隨機的字符串（假設有一組固定的字符串，例如字母A-Z）。如果我事先知道字符串的長度是多少，我可以通過隨機選擇字符串中的每個字符來輕鬆選擇一個隨機字符串。然而，爲了保證我們隨機抽取字符串，我不能隨便選擇一個隨機的長度，然後選擇一個隨機長度的字符串，因爲如果你選擇一個完全隨機的字符串，它往往會比沒有由於長字符串比短字符串更長，所以長度比較短的字符串長。

是否有一種已知的算法，用於隨機選擇一個長度最多爲n的字符串？

謝謝！

Answer 1

有26個字符，長度最多爲n。所以串的總數爲：

Total Number of Strings = \sum_{i=1}^n 26^i 

我們需要每一個這些以相等的概率是被選擇：

P(string s is chosen) = 1/TotalNumStrings 

現在考慮你提出選擇一個隨機的長度，然後選擇的策略一個隨機的那個長度的字符串。因此，通過貝葉斯法則，我們有：

P(string s being chosen which has length i) = 
    P(string s being chosen | string has length i) * 
    P(we want a string of length i) = (1/26^i) * (1/n) = 1/(26^i * n) 

這不等於1/TotalNumStrings。你已經知道這是行不通的，但是這激發了正確的選擇策略。

現在選擇的字符串如下：

P(string s being chosen which has length i) = 
    P(string s being chosen | string has length i) * 
    P(we want a string of length i) = 
     1/(26^i) * P(chosen string has length i) = 1/NumStrings. 

因此，我們有P（選擇的字符串具有長度i）= 26^I/NumStrings！田田。

所以總結一下選擇策略如下。首先選擇長度爲i，概率爲26^i/NumStrings。然後在該類別中選擇一個任意字符串。

Answer 2

每個字母增加了可能字符數的另一個因子，所以有26個單字母字符串，26×26個雙字母字符串等等。你只需要首先隨機選擇一個長度。

例如你可以選擇最多308915776一個隨機數，並選擇字符串的長度如下：

< 26  - 1 
< 702  - 2 
< 15576  - 3 
< 456976 - 4 
< 11881376 - 5 
< 308915776 - 6 

，這些數字變得有點大快十歲上下，雖然如此，這可能工作，只要你ñ小。否則，您可以使用浮點數並使用0到1之間的範圍。

Answer 3

難道你不能只是給出字符集大小的長度分佈？

確定長度爲k的字符串與長度小於k的字符串的比率。這從如下：wikipedia。

因此，假設一個最大的字符串，然後隨機確定一個較短的字符串的相對機會。

如果更短重複看看n-1或更少。

我認爲這種方法合理地處理舍入錯誤乾淨。實際得到一個很短的字符串的機會，當n是合理的大小仍然非常小，但具有代表性。

要做到的款項，我們希望：

k^n samples of length n 
k^(n-1) of length n-1 
etc. 
k of length 1 
1 of length 0 

p(length < x)/p(length <= x) 
= sum(1+..+k^x-1)/sum(1+..+k^x) 
= (1 - k^-x)/ (k-k^-x) 

因此，我們可以實現這樣的：

int getLength(int n, int setSize) 
{ 
    if (n == 0) 
     return 0; 
    double oneOverKtoTheN = pow(1.0/setSize, (double)n); 
    double pLengthN = (1-oneOverKtoTheN)/(setSize - oneOverKtoTheN); 
    double sample = ((double) rand())/RAND_MAX; 
    if (sample < pLengthN) 
     return n; 
    return getLength(n-1, setSize); 
} 

注意如何oneOverKtoTheN可能是由於浮點下手下降，但作爲n減少它開始計數應該。

Answer 4

n減去均勻隨機串的長度的分佈與X mod（n + 1）相同，其中X是具有範圍[0，無窮大）的幾何並且成功概率爲1-1/k並且k是字母表中的字母數量。要隨機選擇一個完全一致的字符串，而不訴諸於bignums：對幾何mod（n + 1）進行採樣（例如，通過均勻採樣字母，直到不是A的字符出現，然後返回非As生成的mod的數量（的n + 1））。生成一個長度爲n的字符串減去該值。

Answer 5

如果您需要稍大的字符串，另一種方法是從27個字符中隨機構建每個字符串，其中第27個字符是字符串末尾字符。您將不得不拒絕任何比您的最大可接受的n更長的字符串，但生成應該相當有效。所以，產生隨機字符串，在範圍0「正確」的分佈和長度爲n，你可以使用下面的更高效的版本：

Function RandomString(n : integer) : string; 
var 
    RandomChar : char; 
begin 
    result := ''; 
    repeat 
    RandomChar := Char('a' + Random(27)); 
    if RandomChar in ['a'..'z'] then 
     result := result + RandomChar; 
    if Length(result) > n then 
     result := ''; 
    until RandomChar not in ['a'..'z']; 
end; 

Answer 6

所有字符串數高達長度n是(26^(n+1)-1)/(26-1)。

想法是確定字符串是否爲空。可能性是(26-1)/(26^(n+1)-1)。爲了生成這樣的概率事件，我們生成事件26^(n+1)，忽略其中一個事件，並從其餘事件中選擇25個事件。

char GenerateRandomCharacter() 
{ 
    ... 
} 
std::string GenerateRandomStringOfFixedLength(int length) 
{ 
    std::string result; 
    for(int c=0;c<length;++c) 
     result.push_back(c); 
    return result; 
} 
bool WillWeGenerateEmptyString(int maxLength) 
{ 
    while(true) 
    { 
     const std::string sample=GenerateRandomStringOfFixedLength(maxLength+1); 
     if(sample==std::string(maxLength+1,'A')) 
      continue;//this leaves 26^n-1 values 
     else 
      return sample.substr(1)==std::string(maxLength,'A');//only 25 strings satisfy this 
    } 
} 
std::string Generate(int maxLength) 
{ 
    if(WillWeGenerateEmptyString(maxLength)) 
     return std::string(); 
    else 
    { 
     std::string result; 
     result.push_back(GenerateRandomCharacter()); 
     result+=Generate(maxLength-1); 
     return result; 
    } 
}