由网友(- Heart)分享简介：我想生成一个随机字符串（或一系列的随机字符串，允许重复），1和 N 字符之间的长度从一些（有限的）字母。每个字符串应该是同等可能（换言之，该字符串应该是均匀分布）。I would like to generate a random string (or a series of random strings, repe...

我想生成一个随机字符串（或一系列的随机字符串，允许重复），1和 N 字符之间的长度从一些（有限的）字母。每个字符串应该是同等可能（换言之，该字符串应该是均匀分布）。

I would like to generate a random string (or a series of random strings, repetitions allowed) of length between 1 and n characters from some (finite) alphabet. Each string should be equally likely (in other words, the strings should be uniformly distributed).

均匀性要求意味着，像这样一个算法不工作：

The uniformity requirement means that an algorithm like this doesn't work:

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

（伪code，兰特（A，B）返回介于 A 和 B （含），每个整数同样有可能）

(pseudo code, rand(a, b) returns a integer between a and b, inclusively, each integer equally likely)

此算法生成与均匀分布的长度的字符串，但实际分配应朝更长的字符串（有26倍之多字符串长度2，因为有长度为1，依此类推。）我怎样才能做到这一点加权？

This algorithm generates strings with uniformly distributed lengths, but the actual distribution should be weighted toward longer strings (there are 26 times as many strings with length 2 as there are with length 1, and so on.) How can I achieve this?

推荐答案

您需要做的就是生成你的长度，然后你的字符串作为两个不同的步骤。您需要首先选择使用加权的办法长度。你可以计算出一个给定长度→的串数为 k的字母为 K ^→。总结这些了，然后你有任何长度的字符串的总数量，你的第一个步骤是生成和1之间的随机数的值，然后垃圾桶相应。模关闭一个错误，你将打破在26，26 ^ 2，26 ^ 3，26 ^ 4等。基于符号的数目的对数将是这个任务是有用的。

What you need to do is generate your length and then your string as two distinct steps. You will need to first chose the length using a weighted approach. You can calculate the number of strings of a given length l for an alphabet of k symbols as k^l. Sum those up and then you have the total number of strings of any length, your first step is to generate a random number between 1 and that value and then bin it accordingly. Modulo off by one errors you would break at 26, 26^2, 26^3, 26^4 and so on. The logarithm based on the number of symbols would be useful for this task.

一旦你有你的长度，那么你可以根据你上面生成的字符串。

Once you have you length then you can generate the string as you have above.