3

假设我想从所有长度最多为 n 的字符串中选择一个均匀随机的字符串（假设字符串可以由一组固定的字符组成，例如字母 A - Z）。如果我事先知道字符串的长度是多少，我可以通过均匀地随机选择该字符串的每个字符来轻松选择一个随机字符串。但是，为了保证我们随机均匀地挑选字符串，我不能只挑选一个均匀随机长度然后挑选一个该长度的随机字符串，因为如果你要挑选一个完全随机的字符串，它通常会有一个长度比短的要大，因为长字符串比短字符串多。

是否有一种已知的算法可以随机均匀地选择长度最多为 n 的字符串？

谢谢！

4

6 回答 6

3

n 的分布减去均匀随机字符串的长度与 X mod (n+1) 相同，其中 X 是范围为 [0, 无穷大) 的几何，成功概率为 1-1/k，k 是字母的数量在字母表中。要随机均匀地选择一个字符串而不使用 bignums：对几何模 (n+1) 进行采样（例如，通过均匀地对字母进行采样，直到出现一个不是 A 的字母，然后返回非 A 生成的模的数量（ n+1))。生成长度为 n 减去该值的字符串。

于 2013-04-07T23:33:22.840 回答
2

每个字母都增加了可能字符数的另一个因子，因此有 26 个单字母字符串、26 × 26 个双字母字符串，依此类推。您只需要先通过相应的缩放来随机选择一个长度。

例如，您最多可以选择一个随机数 308915776 并选择字符串长度，如下所示：

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

不过，这些数字很快就会变得有点大，所以只要你的n很小，它就可以工作。否则，您可以使用浮点数并使用 0 到 1 之间的范围。

于 2013-04-07T23:19:44.407 回答
2

有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(chosen string has length i) = 26^i / NumStrings！多田。

所以总结选择策略如下。首先选择长度 i，概率为 26^i / NumStrings。然后在该类别中选择一个任意字符串。

于 2013-04-07T23:24:37.510 回答
0

给定字符集的大小，您不能只计算长度的分布吗？

确定长度k字符串与长度小于 的字符串的比率k。这来自：维基百科。

因此，假设一个最大字符串，然后随机确定较短字符串的相对机会。

如果较短重复，看看是否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减少，它开始按原样计算。

于 2013-04-07T23:22:02.770 回答
0

不超过长度的所有字符串的数量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;
    }
}
于 2013-04-08T05:18:01.260 回答
-1

如果您需要更大的字符串，另一种方法是从 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;
于 2013-04-07T23:41:25.300 回答