Ещё почти про работу :)

[livelight]

Алгоритмическая задачка

Вдохновившись Кодом Грэя (очень удобен для подбора некоторых кодовых замков, например), а также родственными ему Алгоритмом Нарайаны и алгоритмом Хипа, которые позволяют строить полные наборы всех возможных комбинаций чего-нибудь без дубликатов, каждый раз меняя совсем по чуть-чуть, заинтересовался алгоритмической задачей, про которую гугль услужливо подсказал, что она называется Последовательность де Брёйна: построить такую минимальную последовательность, которая содержит все возможные комбинации длины n из k цифр.

Википедия приводит примеры только для k=2 и всяческих n, я пошёл с обратной стороны: всяческие k и разнообразные n, и на построение всех возможных последовательностей не замахивался, меня интересует построение какой-нибудь, но обязательно кратчайшей.

Для n=2 и любого k последовательность строится элементарно, вот, например, для k=5:
3344001122302413142032104[3...] -- последняя цифра в скобках входит уже в следующий цикл, а цикл имеет длину k^n = 5^2 = 25
Алгоритм простой: берём произвольную первую цифру, дальше в цикле: в первый раз увидев в конце уже построенной последовательности цифру 0, дописываем после неё 0, в следующий раз - 1 и т.д. Увидев в первый раз цифру 1, дописываем после неё 1, в следующий раз - 2 и т.д. Увидев в первый раз цифру 4, дописываем после неё 4, в следующий раз - 0 и т.д. по кругу. И так пока не построим всю последовательность.

Потом я попытался приспособить этот алгоритм к случаю n=3, и тут началось самое интересное.
Принцип тот же: выбираем две первые цифры последовательности, и для каждой упорядоченной пары цифр выбираем, какую цифру допишем после неё, встретив её в первый раз, ну а дальше инкремент и по кругу. И вот тут началось забавное:

* Стратегия: для каждой пары (i,j) в первый раз дописываем 0
Работает, только если начать последовательность с пары (k-1,k-1)
// Напоминаю, что цифры считаются от 0 до k-1 включительно
// Например, для k=4: 3300010020030110120130210220230310320331112113122123132133222323[33..]

* Стратегия: для каждой пары (i,j) в первый раз дописываем i
Работает только для k=1 и 2 при любом начале последовательности.
Не работает при k>2 -- тоже при любом начале последовательности

* Стратегия: для каждой пары (i,j) в первый раз дописываем j
Работает, только если начать последовательность с пары вида (t,t-1)
// для t=0, t-1 = k-1
// Например, для k=4 и t=2: 2111222333000113311002200332212301201302312131323202030310102103[21...]

* Стратегия: для каждой пары (i,j) в первый раз дописываем j+1 (mod k)
Не работает

* Стратегия: для каждой пары (i,j) в первый раз дописываем: i==j ? j : j+1
Работает, только если начать последовательность с пары вида (t,t) или (t,t-1)
// Например, для k=4 и t=1:
// 1012301302312010202121313232030310321000111222333002200331133221[10...]
// 1112301201302312122232333030001011313202031021331103210022003322[11...]

Такой стратегии для n=3, чтобы работала для любого k и любых начальных цифр, не придумал пока.
За бОльшие n браться боюсь, да и выходные уже кончаются, а мне ещё состав до Бологого толкать бигдату в постгрес упихивать :)