Навеяно конкурсом по лабиринту.

На двери висит цифровой замок с последовательным нажатием кнопок.

Код состоит из 2-3-4 цифр (в общем случае — N, где N известно, N>=2).
Порядок цифр в коде может быть существенным или несущественным (123 = 231).
Цифры в коде могут повторяться либо не повторяться.

В замке — сдвиговый регистр, поэтому как только в последовательности нажатий встретится код, он отопрет дверь.

Вопрос: какова минимальная последовательность, гарантированно отпирающая замок?

Очевидно, что оценка сверху — это (D^N)*N (D — число кнопок): вводим N-значные числа одно за другим.
оценка снизу — (D^N)+N-1: все N-значные числа накладываются друг на друга.

Задачи:

Написать программу, порождающую минимальную последовательность.

Или близкую к минимальной.

С учетом того, что длина последовательности растет экспоненциально, рожать последовательность с фиксированными затратами памяти

Еще несколько интересных вопросов:

Какова вероятность отпирания замка равномерно-случайной последовательностью? То есть — какова средняя длина такой последовательности? Как она соотносится с гарантированной?

Есть ли неравномерно случайные последовательности (например, марковские), которые более оптимальны?

Если N неизвестно, но лежит в диапазоне [N1..N2], и предполагается, что меньшие значения N вероятнее больших, то как оптимизировать гарантированную последовательность?

Вот, нагородил в ассортименте.

---

Такие замки (и эквивалентные им) вполне распространены. В том числе — сейфовые крутилки "20 влево, 20 вправо, шаг вперед и два назад".