什麼是數字的字符串最短，其中包含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」）。