什么是数字的字符串最短，其中包含0和1000

Question

我坐在书桌前，我只是想了一个问题，如果任何人都可以想出一个解决方案或方法来证明我想知道之间的所有号码这在数学上。

假设我想查找最短的数字串，其中包含0到1000之间的每个数字。例如，字符串“1433”包含数字1,4,3,14,43,33,143，和433.

什么算法可我用构建含有所有数字0-1000最短的字符串。

我没有为什么我想知道的任何实际的原因，但我很感兴趣地听到，如果有一个。

Answer 1

您所要求的修改de Bruijn sequence。具体来说，一个de Bruijn序列在字符串末尾附加了前n-1个字符。

对于你询问的特定情况，它将是10^3 + 2 = 1002个数字长（假设1000不包括在内 - 你可以安排1000个字符串，如果你设置的东西右上角，但不能保证任意选择的（10,3）de Bruijn序列将包含“1000”）。