如何生成长度不超过特定长度的随机字符串?

您需要做的是将长度和字符串生成为两个不同的步骤。您需要首先使用加权方法选择长度。可以计算给定长度的字符串数 l 一个字母表 k 符号为 k^l . 把这些加起来,得到任意长度的字符串总数,第一步是生成一个介于1和该值之间的随机数,然后对其进行相应的装箱。如果有一个错误,你会在26,26^2,26^3,26^4处,以此类推。基于符号数量的对数对于此任务很有用。

一旦有了长度,就可以像上面那样生成字符串。

好吧,一个字符串有26种可能,26 ^二 对于2个字符的字符串,等等,最多26个 ^二十六 26个字符字符串的可能性。

这意味着(n)字符串的可能性是(n-1)字符串的26倍。你可以用这个事实来选择你的长度:

def getlen(maxlen):
    sz = maxlen
    while sz != 1:
        if rnd(27) != 1:
            return sz
        sz--;
    return 1

我在上面的代码中使用27,因为从“ab”中选择字符串的总样本空间是26个1字符的可能性,26个 ^二 两个字符的可能性。换句话说,这个比率是1:26,所以1个字符的概率是1/27(而不是我第一次回答的1/26)。

这个解决方案不是 很完美 既然你打电话来 rnd 多次,最好一次调用,范围可能是26 ⁿ + 26 ^N-1 + 26 ^一 并根据返回的数字所处的位置选择长度,但可能很难找到一个随机数生成器,它可以处理较大的数字(10个字符为您提供26个可能的范围 ^十 +…+26号 ^一 除非我算错了,否则是146813779479510)。

如果你能限制最大尺寸 RND 函数将在范围内工作,类似这样的操作应该是可行的:

def getlen(chars,maxlen):
    assert maxlen >= 1
    range = chars
    sampspace = 0
    for i in 1 .. maxlen:
        sampspace = sampspace + range
        range = range * chars
    range = range / chars
    val = rnd(sampspace)
    sz = maxlen
    while val < sampspace - range:
        sampspace = sampspace - range
        range = range / chars
        sz = sz - 1
    return sz

一旦你有了长度,我将使用你当前的算法来选择实际的字符来填充字符串。

进一步解释:

假设我们的字母表只包含“AB”。长度为3的可能设置为 [ab] (2) [ab][ab] (4)和 [ab][ab][ab] (8)。所以有8/14的机会得到3的长度,4/14的长度2和2/14的长度1。

14是神奇的数字:它是所有2的总和 ⁿ n=1到最大长度。所以,测试上面的伪代码 chars = 2 和 maxlen = 3 :

    assert maxlen >= 1 [okay]
    range = chars [2]
    sampspace = 0
    for i in 1 .. 3:
        i = 1:
            sampspace = sampspace + range [0 + 2 = 2]
            range = range * chars [2 * 2 = 4]
        i = 2:
            sampspace = sampspace + range [2 + 4 = 6]
            range = range * chars [4 * 2 = 8]
        i = 3:
            sampspace = sampspace + range [6 + 8 = 14]
            range = range * chars [8 * 2 = 16]
    range = range / chars [16 / 2 = 8]
    val = rnd(sampspace) [number from 0 to 13 inclusive]
    sz = maxlen [3]
    while val < sampspace - range: [see below]
        sampspace = sampspace - range
        range = range / chars
        sz = sz - 1
    return sz

因此,在该代码中,最终循环的第一次迭代将退出 sz = 3 如果 val 大于或等于 sampspace - range [14 - 8 = 6] . 换言之,对于值6到13,包括14种可能性中的8种。

否则, sampspace 变成 采样空间-范围[14-8=6] 和 range 变成 range / chars [8 / 2 = 4] .

然后,最终循环的第二次迭代将退出 sz = 2 如果 瓦尔 大于或等于 sampspace - range [6 - 4 = 2] . 换言之,对于值2到5,包含14种可能性中的4种。

否则, 采样空间 变成 采样空间-范围[6-4=2] 和 范围 变成 range / chars [4 / 2 = 2] .

然后,最终循环的第三次迭代将退出 sz = 1 如果 瓦尔 大于或等于 sampspace - range [2 - 2 = 0] . 换句话说,对于值0到1(包括1),14种可能性中的2种(此迭代将 总是 退出,因为该值必须大于或等于零。

回想起来,第二种解决方案有点像噩梦。在我个人看来,我会选择第一种解决方案,因为它很简单,并且避免了出现大量数据的可能性。

根据我发表的评论作为对OP的回复:

我认为这是一个基础训练 转换。你只是在生成 “基数26”中的“随机数”,其中 A=0,Z=25。对于一个随机的字符串 长度n,生成1之间的数字 和26^N。从基数10转换为基数 26,使用你选择的符号 字母表。

这是一个php实现。我不能保证这里没有一两个错误,但是这样的错误应该是很小的:

<?php
$n = 5;

var_dump(randstr($n));

function randstr($maxlen) {
        $dict = 'abcdefghijklmnopqrstuvwxyz';
        $rand = rand(0, pow(strlen($dict), $maxlen));
        $str = base_convert($rand, 10, 26);
        //base convert returns base 26 using 0-9 and 15 letters a-p(?)
        //we must convert those to our own set of symbols
        return strtr($str, '1234567890abcdefghijklmnopqrstuvwxyz', $dict);
}

不要选择均匀分布的长度,而是根据给定长度的字符串数对其进行加权。如果你的字母表是M码,就有M码 ^X 尺寸为x和(1-m)的字符串 ^{N+ 1} )/(1-m)长度不超过n的字符串。选择长度为x的字符串的概率应为m ^X *(1-m)/(1-m ^{N+ 1} )

编辑:

关于溢出-使用浮点而不是整数将扩展范围,因此对于26个字符的字母表和单精度浮点,直接权值计算不应溢出n<26。

一种更健壮的方法是迭代地处理它。这也应尽量减少底流的影响:

int randomLength() {
  for(int i = n; i > 0; i--) {
    double d = Math.random();
    if(d > (m - 1) / (m - Math.pow(m, -i))) {
      return i;
    }
  }
  return 0;
}

为了通过计算更少的随机数来提高效率,我们可以通过在多个位置拆分间隔来重用它们:

int randomLength() {
  for(int i = n; i > 0; i -= 5) {
    double d = Math.random();
    double c = (m - 1) / (m - Math.pow(m, -i))
    for(int j = 0; j < 5; j++) {
      if(d > c) {
        return i - j;
      }
      c /= m;
    }
  }
  for(int i = n % 0; i > 0; i--) {
    double d = Math.random();
    if(d > (m - 1) / (m - Math.pow(m, -i))) {
      return i;
    }
  }
  return 0;
}

编辑:这个答案不太正确。见底部的反证。我暂且不谈,希望有人能想出一个能修复它的变种。

不需要分别计算长度就可以做到这一点,正如其他人所指出的,这需要将一个数提升到一个大的幂,而且在我看来,这通常是一个混乱的解决方案。

证明这是正确的有点困难,我不确定我是否相信我的解释力能把它说清楚,但请容忍我。出于解释的目的,我们最多生成长度为 n 从字母表 a 属于 |a| 角色。

首先,假设你有一个 n ,并且您已经决定生成至少长度为 n-1 . 很明显 |a|+1 同样可能的可能性:我们可以生成 αa 字母表中的字符,或者我们可以选择以 N-1 角色。为了决定,我们只需选择一个随机数 x 之间 0 和 αa (包括在内);如果 X 是 αa ,我们终止于 N-1 字符;否则,我们附加x ^钍 字符串的字符。下面是这个过程在python中的一个简单实现:

def pick_character(alphabet):
  x = random.randrange(len(alphabet) + 1)
  if x == len(alphabet):
    return ''
  else:
    return alphabet[x]

现在,我们可以递归地应用它。生成k ^钍 字符串的字符,我们首先尝试在 k . 如果递归调用返回任何内容,那么我们知道字符串至少应该是长度 K ,然后我们根据字母表生成自己的字符并返回。但是,如果递归调用不返回任何内容,我们知道字符串不长于 K ,我们使用上面的例程选择最终字符或不选择字符。下面是在python中实现的:

def uniform_random_string(alphabet, max_len):
  if max_len == 1:
    return pick_character(alphabet)
  suffix = uniform_random_string(alphabet, max_len - 1)
  if suffix:
    # String contains characters after ours
    return random.choice(alphabet) + suffix
  else:
    # String contains no characters after our own
    return pick_character(alphabet)

如果你怀疑这个函数的一致性,你可以尝试反驳它:建议一个字符串,它有两种不同的生成方法,或者没有。如果没有这样的字符串-唉,我没有这一事实的有力证明,尽管我相当肯定这是真的-并且考虑到各个选择是一致的,那么结果还必须选择任何具有一致概率的字符串。

正如我们所承诺的,与迄今为止发布的所有其他解决方案不同,不需要将数字提升到大的幂;不需要任意长度的整数或浮点数来存储结果,并且有效性,至少在我看来,是相当容易证明的。到目前为止,它比任何完全指定的解决方案都要短。;)

如果有人想提供函数一致性的可靠证明,我将非常感激。

编辑:反证,朋友提供:

dato: so imagine alphabet = 'abc' and n = 2
dato: you have 9 strings of length 2, 3 of length 1, 1 of length 0
dato: that's 13 in total
dato: so probability of getting a length 2 string should be 9/13
dato: and probability of getting a length 1 or a length 0 should be 4/13
dato: now if you call uniform_random_string('abc', 2)
dato: that transforms itself into a call to uniform_random_string('abc', 1)
dato: which is an uniform distribution over ['a', 'b', 'c', '']
dato: the first three of those yield all the 2 length strings
dato: and the latter produce all the 1 length strings and the empty strings
dato: but 0.75 > 9/13
dato: and 0.25 < 4/13

// Note space as an available char
alphabet = "abcdefghijklmnopqrstuvwxyz "

result_string = ""

for( ;; )
{
    s = ""

    for( i = 0; i < n; i++ )
        s += alphabet[rand(0, 26)]

    first_space = n;

    for( i = 0; i < n; i++ )
        if( s[ i ] == ' ' )
        {
            first_space = i;
            break;
        }

    ok = true;

    // Reject "duplicate" shorter strings
    for( i = first_space + 1; i < n; i++ )
        if( s[ i ] != ' ' )
        {
            ok = false;
            break;
        }

    if( !ok )
        continue;

    // Extract the short version of the string
    for( i = 0; i < first_space; i++ )
        result_string += s[ i ];

    break;
}

编辑:我忘了禁止0长度的字符串,这将需要更多的代码,我现在没有时间添加。

编辑:考虑到我的答案没有扩展到大N(需要很长时间才能幸运地找到一个可接受的字符串),我更喜欢PaxDiablo的答案。代码也少了。

我个人会这样做:

假设你的字母表 Z 角色。则每个长度的可能字符串数 L 是:

L | Z
--------------------------
1 | 26
2 | 676 (= 26 * 26)
3 | 17576 (= 26 * 26 * 26)

……等等。

假设你想要的最大长度是 N . 那么从长度1到 n 你的函数可以生成 the sum of a geometric sequence :

(1 - (Z ^ (N + 1))) / (1 - Z) 

我们称这个值为 S . 那么生成任意长度字符串的概率 L 应该是:

(Z ^ L) / S

好吧,好吧。这一切都很好,但是我们如何在非均匀概率分布下生成一个随机数呢?

简单的回答是:你不需要。找个图书馆来帮你。我主要在.net中开发,所以我可能会转向 Math.NET 。

也就是说,其实不是 所以 很难想出一个简单的方法来自己做这件事。

有一种方法:使用一个生成器,在已知的 制服 分布,并根据所需分布在该分布中的大小指定范围。然后通过确定生成器所属的范围来解释生成器提供的随机值。

下面是一个用c表示的实现这个想法的方法的示例(滚动到底部,例如输出):

RandomStringGenerator 班

public class RandomStringGenerator
{
    private readonly Random _random;
    private readonly char[] _alphabet;

    public RandomStringGenerator(string alphabet)
    {
        if (string.IsNullOrEmpty(alphabet))
            throw new ArgumentException("alphabet");

        _random = new Random();
        _alphabet = alphabet.Distinct().ToArray();
    }

    public string NextString(int maxLength)
    {
        // Get a value randomly distributed between 0.0 and 1.0 --
        // this is approximately what the System.Random class provides.
        double value = _random.NextDouble();

        // This is where the magic happens: we "translate" the above number
        // to a length based on our computed probability distribution for the given
        // alphabet and the desired maximum string length.
        int length = GetLengthFromRandomValue(value, _alphabet.Length, maxLength);

        // The rest is easy: allocate a char array of the length determined above...
        char[] chars = new char[length];

        // ...populate it with a bunch of random values from the alphabet...
        for (int i = 0; i < length; ++i)
        {
            chars[i] = _alphabet[_random.Next(0, _alphabet.Length)];
        }

        // ...and return a newly constructed string.
        return new string(chars);
    }

    static int GetLengthFromRandomValue(double value, int alphabetSize, int maxLength)
    {
        // Looping really might not be the smartest way to do this,
        // but it's the most obvious way that immediately springs to my mind.
        for (int length = 1; length <= maxLength; ++length)
        {
            Range r = GetRangeForLength(length, alphabetSize, maxLength);
            if (r.Contains(value))
                return length;
        }

        return maxLength;
    }

    static Range GetRangeForLength(int length, int alphabetSize, int maxLength)
    {
        int L = length;
        int Z = alphabetSize;
        int N = maxLength;

        double possibleStrings = (1 - (Math.Pow(Z, N + 1)) / (1 - Z));
        double stringsOfGivenLength = Math.Pow(Z, L);
        double possibleSmallerStrings = (1 - Math.Pow(Z, L)) / (1 - Z);

        double probabilityOfGivenLength = ((double)stringsOfGivenLength / possibleStrings);
        double probabilityOfShorterLength = ((double)possibleSmallerStrings / possibleStrings);

        double startPoint = probabilityOfShorterLength;
        double endPoint = probabilityOfShorterLength + probabilityOfGivenLength;

        return new Range(startPoint, endPoint);
    }
}

Range 结构

public struct Range
{
    public readonly double StartPoint;
    public readonly double EndPoint;

    public Range(double startPoint, double endPoint)
        : this()
    {
        this.StartPoint = startPoint;
        this.EndPoint = endPoint;
    }

    public bool Contains(double value)
    {
        return this.StartPoint <= value && value <= this.EndPoint;
    }
}

试验

static void Main(string[] args)
{
    const int N = 5;
    const string alphabet = "acegikmoqstvwy";
    int Z = alphabet.Length;

    var rand = new RandomStringGenerator(alphabet);

    var strings = new List<string>();
    for (int i = 0; i < 100000; ++i)
    {
        strings.Add(rand.NextString(N));
    }

    Console.WriteLine("First 10 results:");
    for (int i = 0; i < 10; ++i)
    {
        Console.WriteLine(strings[i]);
    }

    // sanity check
    double sumOfProbabilities = 0.0;

    for (int i = 1; i <= N; ++i)
    {
        double probability = Math.Pow(Z, i) / ((1 - (Math.Pow(Z, N + 1))) / (1 - Z));
        int numStrings = strings.Count(str => str.Length == i);

        Console.WriteLine("# strings of length {0}: {1} (probability = {2:0.00%})", i, numStrings, probability);

        sumOfProbabilities += probability;
    }

    Console.WriteLine("Probabilities sum to {0:0.00%}.", sumOfProbabilities);

    Console.ReadLine();
}

输出:

First 10 results:
wmkyw
qqowc
ackai
tokmo
eeiyw
cakgg
vceec
qwqyq
aiomt
qkyav
# strings of length 1: 1 (probability = 0.00%)
# strings of length 2: 38 (probability = 0.03%)
# strings of length 3: 475 (probability = 0.47%)
# strings of length 4: 6633 (probability = 6.63%)
# strings of length 5: 92853 (probability = 92.86%)
Probabilities sum to 100.00%.

我的想法是:

有1-n个长度的字符串。有26个可能的1个长度的字符串,26*26个2个长度的字符串等等。 您可以找出每个长度字符串占可能字符串总数的百分比。例如,单个长度字符串的百分比如下

((26/(全部长度的可能字符串总数)*100)。

类似地,您可以找出其他长度字符串的百分比。 将它们标记在1到100之间的数字行上。即假设单长字符串的百分比为3,双长字符串的百分比为6,则数字行单长字符串介于0-3之间,而双长字符串介于3-9之间,依此类推。 现在取一个介于1到100之间的随机数。找出这个数的范围。我的意思是假设你随机选择的数字是2。现在这个数字在0到3之间,所以选择1个长度的字符串,或者如果选择的随机数是7,那么选择双长度的字符串。

以这种方式,您可以看到每个选择的字符串的长度将与该长度字符串占所有可能字符串总数的百分比成比例。

希望我明白了。 免责声明:除了一两个解决方案,我没有经历过以上的解决方案。因此,如果它与某个解决方案相匹配,那纯粹是一个机会。 同时,我欢迎所有的建议和正面的批评,如果我错了,我会纠正我。

感谢和尊敬 马维亚

马蒂厄:你的想法行不通,因为带空格的字符串仍然更有可能被生成。在您的例子中,如果n=4,则可以将字符串“a b”生成为“a”+“b”+''+''+''或'+“a”+“b”+'',或其他组合。因此,并非所有的弦都有相同的出现机会。