什么是包含0到1000之间所有数字的最短数字字符串？

Question

什么是包含0到1000之间所有数字的最短数字字符串？

4

我坐在桌前，突然想到一个问题，想知道有没有人能够想出一个解决方案或者通过数学方法证明。问题是：如何找到一个最短的数字串，使得它包含了从0到1000之间的所有数字。例如，数字串“1433”包含数字1、4、3、14、43、33、143和433。

你可以使用什么算法来构建包含所有0-1000数字的最短数字串呢？

我并没有实际应用的需求，但如果有的话，我很感兴趣听到它们。

- bramp

乍一看，它看起来是NP完备的。但这只是一个猜测而已。 - Marcelo Cantos

http://answers.google.com/answers/threadview/id/21050.html 可能会有所帮助。 - lijie

请参见https://dev59.com/1W865IYBdhLWcg3wEKOZ。 - BlueRaja - Danny Pflughoeft

我来问同样的问题，只是针对所有00000到55555的序列使用基数5 -- 我想测试我的汽车无钥匙进入键盘的安全性。为此，我在网上找到了一个示例超级字符串，但我想找到可能最短的字符串。看起来https://dev59.com/1W865IYBdhLWcg3wEKOZ有最接近的解决方案。 - Dinah

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stephen Canon · Accepted Answer

你正在寻求一个修改过的德布鲁因序列。具体来说，是在字符串末尾附加前n-1个字符的德布鲁因序列。

对于你所询问的特定情况，它将有1002位数字（假设不包括1000 -- 如果设置正确，你也可以让1000出现在字符串中，但是任意选择的(10,3) 德布鲁因序列不保证包含 "1000"）。