真正大排列表

我的问题不是语言特定的。我遇到了处理排列循环的问题。我试图编写一些代码来显示26^x的所有值，其中x是字符串的长度。没有输入的字符串会被提供，所以如果x=1，它会通过ž显示一个，如果x=2 ITLL显示AA通过ZZ。 az被认为不同于za。真正大排列表

更具体地说，我想运行这个更长的字符串，长度超过100个字符，试图查看给定长度的字符串包含多少个字符而不是随机字母。

来源

2012-04-13 Rickie Marsh

时间复杂度和单词数量是n !, 100个字符是9 * 10^157。任何算法都需要很长时间才能让这些单词更少地处理它们。 – 2012-04-13 05:07:51

（根据我的理解）您可以计算您的程序生成的长度的单词数量。使用字典库来计算给定长度的字数。现在，您可以看到随机字母的数量。 – 2012-04-13 06:44:48

@JesusRamos你可以掷出一枚公平的硬币1000001次，模拟它将需要2^1000001步，但几乎没有时间预测'头'赢了还是输了！ – ElKamina 2012-04-13 06:52:30

根据对该问题的评论，尝试枚举所有可能的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足够，随机采样就会给出整个空间行为的表示。

来源

2012-04-13 05:15:53 mfrankli

您可以通过将总词数对于每个长度'n'和除以'n！'，这将是长度为'n'的字母串的部分，它们是单词。我认为OP在询问是否将单词作为一个子集，但这很难。 – Dougal 2012-04-13 05:18:06

是的，这也是我的解释（因此我的答案没有多大意义，否则），但代码并没有真正反映出来。正在编辑... – mfrankli 2012-04-13 05:20:22

26^x，其中x是一个字符串的长度...我想长

你应该忘掉它的长字符串运行此，超过100个字符。

让我们来看看事物。英语字母表中有26个字母，因此其中有100个字符的字符串总数是...

3142930641582938830174357788501626427282669988762475256374173175398995908420104023465432599069702289330964075081611719197835869803511992549376

这是十进制数。每毫秒1个字符串的速度将花费9.9 * 10^130年来全部打印。这比宇宙长7.3×10^120倍。

获取单词列表或将字典加载到内存中，然后使用它。

来源

2012-04-13 05:17:51 SigTerm

我明白了这一点。我计划随机使用前两个字符进行手动检查。如果不可能开始一个词，它会放弃这条路。我可能说我的问题错了，因为它更多的是从两个字符开始，检查一个单词是否可能，如果是，则添加另一个字符并重复，直到任何单词不可能或字符串长度已达到。如果不可能，移动到该位置的下一个字母。 – 2012-04-13 06:31:01

通过为前两个字符设置一些简单的规则，可以消除大量的搜索/处理。如果q是第一个，那么第二个只能是元音。其他一些字母也是如此。 26^2可能的两个字母组合，q例如只有5个有效组合，它是第一个字母。虽然设置许多规则仍然没有乐趣，但它确实消除了很多问题。此外，由于我正在考虑在给定位置使用特定单词的字符串，因此可以在单词前后分为两部分。 – 2012-04-16 10:28:58

我们现在想看到的是：有多少个字符串的大小为50,51,52 ......可以从字典中用以下单词构建：“2：183,3：815,4：3181,5： 6151,6：9317,7：11962,8：11979,9：10400,10：8065，......“从{2..20}中的n代替你的值;做echo -ne“$ n \ t”; egrep -v“。*”s“/ usr/share/dict/american-english | egrep -c“^。{”$ n“} $”;完成' – 2012-05-09 19:54:38

这取决于你对'单词'的定义。如果'a'是一个单词，那么获得以100个字符序列获得单词的概率的下限是非常容易的（大致为1 1/e^4）。同样，你可以考虑2个字母的单词和3个字母的单词，并提高概率。在4或5个字母之后，这个概率变得非常准确，因为有几个更长的单词，并且它们随机发生的情况非常罕见。

来源

2012-04-13 06:42:25 ElKamina

给定字符串长度中的多个单词。如果用户输入8，则可以返回“itisadog”或“wesaidno”。这样看，有一本字典，并寻找所有的话加起来到给定的长度似乎更好 – 2012-04-13 10:23:44

@RickieMarsh：但你不指望他们有道理？那么'nosaidwe'和'nonoweno'会适合吗？ – 2012-05-09 16:23:59

真正大排列表

回答

相关问题