algorithm - 是否可以创建一个生成自动图的算法？

Question

安autogram是一个描述它包含的字符的句子，通常列举字母表中的每个字母，但也可能列举它包含的标点符号。这是维基页面中给出的示例。

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 sentence employs”，并假设它使用与上述“x a's, ... y z's”相同的格式。

我并不是要你实际编写算法，尽管无论如何我很想看看你是否知道存在一个算法或者想尝试编写一个算法；相反，我很好奇这个问题是否首先是可计算的。

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."

可计算意味着存在一种算法，对于给定的起始文本，要么输出一个解决方案，要么声明没有解决方案。上述算法无法做到这一点，穷举搜索是行不通的。因此我会说这个问题是不可计算的。然而，这更具有学术意义。在实践中，随机算法工作得很好。