有没有可能创建一个能够生成自己描述的算法？

Question

自叙语句是一种描述其所包含字符的句子，通常列举出每个字母，但也可能包括其所包含的标点符号。以下是维基页面中给出的例子。

这个句子使用了两个a，两个c，两个d，28个e，五个f，三个g，八个h，十一个i，三个l，两个m，十三个n，九个o，两个p，五个r，二十五个s，二十三个t，六个v，十个w，两个x，五个y和一个z。

编写这样一个句子很难，因为你不知道它包含多少个字母，除非你完成这个句子。这促使我问：是否可能编写一个算法来创建自叙语句？例如，一个给定的参数将作为输入，如"这个句子使用"，并假设它使用与上述相同的格式"x个a，... y个z"。

我并不要求你实际编写算法，虽然我很想知道你是否知道某个算法的存在或者想尝试编写一个；相反，我想知道这个问题是否在计算机中是可计算的。

- Lou

---

我不认为它可以做到。正如我在原帖中指定的那样，我并不要求人们编写算法，而是询问它是否可能存在。这不是一个挑战，而是关于计算普适性的问题。 - Lou

有趣的内容。 - n. m.

@NiklasB。长度有一个上限。 - n. m.

@n.m. 在阅读您的参考资料后，我意识到可以通过利用数字在其书写表示大小方面呈指数增长的事实来证明这一点。因此，当然可以通过详尽搜索（实际上可能需要使用大量修剪的详尽搜索）来解决问题。也许有一个相当简单的整数线性规划公式可以直接输入现代求解器中。 - Niklas B.

@Unihedron，我非常怀疑它是否适合[codegolf.se]，即使它适合，它在这里的位置可能更好。 - Bernhard Barker

Answer 1

你提出了两个不同的问题。

"is it possible to write an algorithm which could create an autogram?"

有用于查找自身句的算法。据我所知，它们使用随机化，这意味着这样的算法可能会为给定的起始文本找到一个解决方案，但如果没有找到，则不代表不存在解决方案。这带我们来到第二个问题。

"I'm curious as to whether the problem is computable in the first place."

可计算的意思是存在一个算法，对于给定的起始文本，要么输出一个解决方案，要么说明没有解决方案。上述算法无法做到这一点，而穷举搜索也不可行。因此，我认为这个问题是不可计算的。然而，这更多地是学术上的兴趣。在实践中，随机算法已经足够好用了。

- Ubik

Answer 2

假设此刻所有计数都小于或等于某个最大值M，其中M<100。正如OP链接中提到的那样，这意味着我们只需要决定出现在这些数字单词中的16个字母的计数，因为其他10个字母的计数已经由指定的前缀文本确定，不能更改。

我认为值得利用的一个属性是，如果我们采用一些（可能不正确的）解决方案并重新排列其中的数字单词，则总字母计数不会改变。换句话说，如果我们忽略花费“命名自己”的字母（例如two c's中的c），则总字母计数仅取决于实际存在于句子中的数字单词的多重集合。这意味着，我们不必考虑将M个数字单词分配给16个字母的所有可能方式，而是可以枚举大小不超过16的所有数字单词的多重集合（元素来自大小为M的数字单词的基础集合），对于每个多重集合，查看是否可以将16个字母适配到其元素上，以使用每个多重集合元素恰好一次。

请注意，数字的多重集可以唯一地表示为非递减的数字列表，这使得它们易于枚举。

“适合”多重集的字母是什么意思？假设我们有一个数字单词的多重集W；这确定了16个字母的总计数（对于每个字母，只需将该字母在W中的所有数字单词中的计数相加；还要为除“one”以外的每个数字单词添加字母“S”的计数，以解决复数问题）。称这些字母计数f [“A”]等为“A”的频率等。假装我们有一个函数etoi()，它像C的atoi()一样运行，但返回数字单词的数值。 （这只是概念性的；当然，在实践中，我们总是从整数值（我们会保留）生成数字单词，而不是相反。）那么，如果且仅当f [x] + 1 = etoi(w)，则字母x适合W中的特定数字单词w，因为将字母x本身写入句子将使其频率增加1，从而使等式的两侧相等。

这还没有解决一个问题，如果有多个字母符合一个数词，只能分配给其中一个。但是，事实证明很容易确定给定数字单词的多重集合W，表示为非递减整数列表，同时适用于任何字母集：

• 计算W所暗示的总字母频率f[]。
• 对这些频率进行排序。
• 跳过任何零频率字母。 假设有k个这样的字母。
• 对于每个剩余字母，检查其频率是否等于对应位置上数词的数值减1。 即检查f[k] + 1 == etoi（W [0]），f [k + 1] + 1 == etoi（W [1]）等。
• 当且仅当所有这些频率都一致时，我们才有赢家！

上述方法是天真的，因为它假设我们从大小为M的集合中选择单词放入多重集合中。对于M>20，该集合中存在许多结构可以被利用，代价是稍微复杂化算法。特别地，与其枚举所有允许数字的基础集合的直接多重集合，不如枚举{"one"，"two"，...，"nineteen"，"twenty"，"thirty"，"forty"，"fifty"，"sixty"，"seventy"，"eighty"，"ninety"}的多重集合，然后允许“拟合检测”步骤将十的倍数的数字-单词与个位数的数字-单词组合起来。

- j_random_hacker

---

我发现你的答案非常复杂，但读起来很有趣；感谢你详细探讨了这个问题！虽然我在你的回答中没有找到与问题相关的参考，即问题是否一般可计算。你认为你所描述的方法是否适用于任何前缀文本？ - Lou

@LeoKing：我的答案是更有效的暴力搜索方法，与显而易见的方法类似，必须在一定限制下停止搜索（这里，每个字母的最大值为M），因此如果M选择得太低，则可能会错过某些解决方案。 - j_random_hacker

@LeoKing：建立可计算性的一种方法是设计一个函数u()，它告诉我们对于任何给定的n值，多重集合中最多包含26个数字单词，其数值总和为n的字母总数的上限；并且具有这样的属性，即对于某个k，u(i+k) <= i+k。如果我们可以找到一段连续的k个值i，使得带内所有值的u(i) < i，则我们知道没有长度为i或更长的句子是可表示的，因此我们可以将M = i。 - j_random_hacker

@LeoKing：我相信这样的算法一定存在，因为我确定随着数字增加，数字单词的总字母数增长速度小于1，尽管有许多需要处理的特殊情况（例如“twenty”->“twenty-one”：所描述的数字仅增加了1，但字母数增加了3> 1），因此您需要采用适当平均的方法。 - j_random_hacker