Какова самая короткая строка чисел, которая содержит все числа от 0 до 1000

Question

Я сидел за своим столом, и я только что придумал проблему, и мне было интересно, может ли кто-нибудь придумать решение или способ математически доказать это.

Скажем, я хотел найти самую короткую строку чисел, которая содержала каждое число от 0 до 1000. Например, строка «1433» содержит числа 1, 4, 3, 14, 43, 33, 143 и 433.

Какой алгоритм я мог бы использовать для построения самой короткой строки, содержащей все числа 0-1000.

У меня нет практической причины, почему я хочу знать, но мне было бы интересно узнать, есть ли такая.

Answer 1

Вы запрашиваете модифицированную последовательность де Брейна . В частности, последовательность де Брюйна с первыми n-1 символами, добавленными в конец строки.

В конкретном случае, о котором вы спрашиваете, он будет иметь длину 10 ^ 3 + 2 = 1002 цифры (при условии, что 1000 не включено - вы можете также указать 1000 в строке, если вы настроите параметры) верно, но нет никакой гарантии, что произвольно выбранная (10,3) последовательность де Брейна будет содержать «1000»).