algorithm - 真的很大的排列列表

Question

我的问题不是特定于语言的。我在让循环处理排列时遇到问题。我正在尝试编写一些代码来显示字符串长度的26^x所有值。x不会提供输入字符串，所以如果x=1它会显示a到z，如果它会x=2显示aa到zz。 az被视为与za不同。

更具体地说，我想为更长的字符串运行它，长度为 100 多个字符，以尝试查看有多少给定长度的字符串包含单词而不是随机字母。

Answer 1

根据对该问题的评论，尝试枚举所有可能的 100 个字符的字符串有些不切实际。

我会建议生成给定长度的随机字符串的替代策略，而不是以结构化方式枚举。就像是：

count = 0
for i from 0 to simulation_length:
    random_string = ''
    for j from 0 to string_length:
        random_string += random_char()
    // containsWord(string) checks if the random string contains a word
    // this is tricky in and of itself
    if (containsWord(random_string)) count++
...

只要simulation_length 足够，随机采样将为您提供整个空间的行为表示。

Answer 2

26^x 其中 x 是字符串的长度...我想为更长的字符串运行它，长度为 100+ 个字符

你应该忘记它。

让我们正确看待事物。英文字母有26个字母，所以100个字符的字符串总数是...

3142930641582938830174357788501626427282669988762475256374173175398995908420104023465432599069702289330964075081611719197835869803511992549376

那是十进制数。以每毫秒 1 个字符串的速度将它们全部打印出来需要 9.9*10^130 年。这比宇宙存在的时间长 7.3*10^120 倍。

获取一个单词列表或将字典加载到内存中并使用它。

Answer 3

这将取决于您对“单词”的定义。如果 'a' 是一个单词，那么很容易得到一个 100 个字符序列中的单词概率的下限（大约 1-1/e^4）。同样，您可以考虑 2 个字母词和 3 个字母词并细化概率。在 4 或 5 个字母之后，这个概率变得非常准确，因为较长的单词很少，而且它们随机出现的情况非常罕见。