如何生成长度达到一定长度的随机字符串？

Question

我想生成一个随机字符串(或一系列随机字符串,允许重复),长度介于1和n字符之间(有限).每个字符串应该具有相同的可能性(换句话说,字符串应该是均匀分布的).

均匀性要求意味着这样的算法不起作用:

alphabet = "abcdefghijklmnopqrstuvwxyz"
len = rand(1, n)
s = ""
for(i = 0; i < len; ++i)
    s = s + alphabet[rand(0, 25)]

(伪代码,rand(a, b)返回一个介于a和之间的整数b,包含每个整数的可能性)

该算法生成具有均匀分布长度的字符串,但实际分布应该朝向更长的字符串加权(长度为2的字符串数量是长度为1的字符串的26倍,依此类推.)如何实现此目的？

Answer 1

你需要做的是生成你的长度,然后你的字符串作为两个不同的步骤.您需要首先使用加权方法选择长度.您可以计算符号l字母表的给定长度的字符串数量.将它们相加,然后你得到任意长度的字符串总数,你的第一步是生成一个介于1和该值之间的随机数,然后相应地对其进行bin.通过一个错误模数,您将在26,26 ^ 2,26 ^ 3,26 ^ 4等处打破.基于符号数的对数对此任务很有用.kk^l

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

Answer 2

好的,1个字符的字符串有26种可能性,2个字符的字符串有26个²,而26 ^个字符的字符串最多有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 ^个 2个字符的可能性.换句话说,比率为1:26,因此1个字符的概率为1/27(而不是我第一次回答的1/26).

这个解决方案并不完美,因为你rnd多次呼叫,最好用26 ^N +26 ^N-1 +26 ¹的可能范围呼叫它,并根据返回的数字在那里的位置选择长度但是可能很难找到一个随机数发生器,它可以处理大数字(10个字符给你的可能范围26 ¹⁰ + ... + 26 ¹除非我做错了数学,否则是146,813,779,479,510 ).

如果您可以限制最大尺寸以使您的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的4/14和长度为1的2/14.

14是神奇的数字:它是n = 1到最大长度的所有2 ⁿ的总和.所以,使用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 = 3if val大于或等于时退出sampspace - range [14 - 8 = 6].换句话说,对于值6到13(包括6和13),14种可能性中的8种.

否则,sampspace变得sampspace - range [14 - 8 = 6]和range变range / chars [8 / 2 = 4].

然后,最后一个循环的第二次迭代将在sz = 2if val大于或等于时退出sampspace - range [6 - 4 = 2].换句话说,对于值2到5(包括两者),14种可能性中的4种.

否则,sampspace变得sampspace - range [6 - 4 = 2]和range变range / chars [4 / 2 = 2].

然后,最后一个循环的第三次迭代将在sz = 1if val大于或等于时退出sampspace - range [2 - 2 = 0].换句话说,对于值0到1(包括0和1),14种可能性中的2种(此迭代将始终退出,因为该值必须大于或等于零.

回想起来,第二种解决方案有点像噩梦.在我个人看来,我会寻求第一个解决方案,因为它简单,并避免相当大的数字的可能性.

Answer 3

不是选择均匀分布的长度，而是根据给定长度的字符串数量对其进行加权。如果你的字母表大小为 m，则有 m ^{x 个}大小为 x 的字符串，以及 (1-m ⁿ⁺¹ )/(1-m) 个长度为 n 或更小的字符串。选择长度为 x 的字符串的概率应为 m ^x *(1-m)/(1-m ⁿ⁺¹ )。

编辑：

关于溢出 - 使用浮点而不是整数会扩大范围，因此对于 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;
}