algorithm - 自签名算法

Question

签名是描述其字母的句子。例如，来自维基百科:

This sentence employs two a’s, two c’s, two d’s, twenty-eight e’s, five f’s, three g’s, eight h’s, eleven i’s, three l’s, two m’s, thirteen n’s, nine o’s, two p’s, five r’s, twenty-five s’s, twenty-three t’s, six v’s, ten w’s, two x’s, five y’s, and one z.

这些句子很难手工创建，因此计算机无疑是最适合这项任务的，但如何才能高效地完成呢？ 查找具有给定初始字符串的自动签名的有效算法是什么？链接签名怎么样，前一句描述下一句的内容？ 而this线程是关于同一主题的，它只是要求存在，并且那里描述的所有算法在实践中都太慢了。

一种天真的方法是搜索可能的数字组合集，例如从 0 到 40，以寻找可能的解决方案。然而，如果有 40^26 种可能性，这将花费不可思议的时间。

我们可以通过从字母组合的一些初始猜测开始，然后仅搜索与我们的猜测在任何一边偏离 3 的自动签名，以可能错过解决方案为代价来改进我们的搜索。这仍然需要 6^26 次。即使以每秒一百万次检查的速度，这也需要超过 500 万年才能完成。

进一步的改进是认识到 a、b、c、d、j、k、m、p、q 和 z 从未出现在任何数字词中，因此这十个字母的计数由初始字符串固定.我们现在只有 3 万亿种组合——仍然不是很好。

最好从初步猜测开始，然后...

1. 创建一个新的“autogram”，它描述了先前 autogram 的字母数
2. 检查我们是否已经重复了一个签名。如果我们有，并且循环长度为 1，我们就完成了。否则，稍微修改猜测并转到步骤 1。

...但这有其公平的局限性。尽管这项任务看似徒劳无功，但其他人却取得了成功。事实上，http://autograms.net/甚至有一连串 25 链接的亲笔签名。怎么办？

Answer 1

执行此操作的一种有效方法是用描述前一个短语的短语替换该短语，直到它们相同，即该短语是一个签名。但在很多情况下它可能不起作用。