Light (livelight) wrote,
Light
livelight

Categories:

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

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

Вдохновившись Кодом Грэя (очень удобен для подбора некоторых кодовых замков, например), а также родственными ему Алгоритмом Нарайаны и алгоритмом Хипа, которые позволяют строить полные наборы всех возможных комбинаций чего-нибудь без дубликатов, каждый раз меняя совсем по чуть-чуть, заинтересовался алгоритмической задачей, про которую гугль услужливо подсказал, что она называется Последовательность де Брёйна: построить такую минимальную последовательность, которая содержит все возможные комбинации длины 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 браться боюсь, да и выходные уже кончаются, а мне ещё состав до Бологого толкать бигдату в постгрес упихивать :)

Оригинал поста: https://livelight.dreamwidth.org/463861.html.
Комментов там: comment count unavailable
Tags: физматпрог
Subscribe

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments