Оптимизация генерации слов Линдона с условиями

[Nartu]

В ходе решения одной задачи(до сих пор в процессе), мне пришлось

создавать все слова Линдона постоянной длины на даных буквах с заданным числом повторений. То есть, делать из элементов мультимножества, на пример $\left\lbrace{a,a,a,b,b,b,c,c}\right\rbrace$ используя все буквы из него

Это обобщение. Мой кейс - поиск для бинарных слов. Я уже спрашивал на Quora и мне ответили, но там предложили не очень эффективный способ.. и работал медленно, может быть, из-за реализации на питоне.
Так же понятно, что если в случае двух букв одна повторяется довольно много - можно получить мало валидных.

Я пока работаю над ним в js. Всё уже и есть, но лучше обрубать цикл на какой-то позиции, поближе к последнему слову, что будет валидно по условию. В идеале на таком слове, которое минимально из тех, кто (лексически) больше всех валидных, скажем, имеющих 5 единиц. Не забываем, что все рассмотреные слова постоянной длины.
( Так же интересен и вариант наоборот: максимальное (с 5 единицами), меньше всех остальных (с 6-ю единицами) )

И вот, либо находить эти.. "критические" слова как-то быстро, либо какие-то части - префиксы/суфиксы проверять, для выхода с цикла генерации. Можно строить какую-то ..характеристику.
(ещё поигравшись с этими строками - возникла совсем отчаянная идея - посмотреть на это как на эволюцию 1-мерного клеточного автомата)

Вообще, это похоже на ситуацию, когда есть последовательность(необычная) и функционал от её элементов. И нам надо найти минимальный элемент со значением функционала, которое больше, чем на всех предыдущих элементах, либо... элементы последовательности, что имеют значения функционала в заданых пределах.
У меня подсчёт единичек в бинарных кодах. НО, лексический порядок слов Линдона такой, что количества единиц то возрастают, то падают...немонотонно. Надо что-то придумать, что бы не сортировать, но избавиться от вот тех прыжков/падений.

Я мог бы показать график числа единичек, но не уверен, что у ЛаТеХа есть функционал для этого. Попросите? - попробую... У меня есть датасет(массив) слов длины 11.. их 186 нашло (у 13 их 630).
Пока выложу просто отфильтрованые слова из всего массива(порядок в слове перевернул! ладно, пусть будет). Как обычно $0<1$ :

$\begin{tabular}{r|c|c} число 1-чек & макс. & мин. больше\\ \hline 1 & 1\,0\,0\,0\,0\,0\,0\,0\,0\,0\,0 & 1\,1\,0\,0\,0\,0\,0\,0\,0\,0\,0 \\ 2 & 1\,0\,0\,0\,0\,1\,0\,0\,0\,0\,0 & 1\,1\,0\,0\,0\,1\,0\,0\,0\,0\,0 \\ 3 & 1\,0\,0\,1\,0\,0\,0\,1\,0\,0\,0 & 1\,1\,0\,1\,0\,0\,0\,1\,0\,0\,0 \\ 4 & 1\,0\,1\,0\,0\,1\,0\,0\,1\,0\,0 & 1\,1\,1\,0\,0\,1\,0\,0\,1\,0\,0 \\ 5 & 1\,0\,1\,0\,1\,0\,1\,0\,1\,0\,0 & 1\,1\,1\,0\,1\,0\,1\,0\,1\,0\,0 \\ 6 & 1\,1\,0\,1\,0\,1\,0\,1\,0\,1\,0 & 1\,1\,1\,1\,0\,1\,0\,1\,0\,1\,0 \\ 7 & 1\,1\,0\,1\,1\,0\,1\,1\,0\,1\,0 & 1\,1\,1\,1\,1\,0\,1\,1\,0\,1\,0 \\ 8 & 1\,1\,1\,0\,1\,1\,1\,0\,1\,1\,0 & 1\,1\,1\,1\,1\,1\,1\,0\,1\,1\,0 \\ 9 & 1\,1\,1\,1\,1\,0\,1\,1\,1\,1\,0 & 1\,1\,1\,1\,1\,1\,1\,1\,1\,1\,0 \\ 10 & 1\,1\,1\,1\,1\,1\,1\,1\,1\,1\,0 & (\,1\,)\\ \end{tabular}$

Примечание: я немного приврал.. мне нужны не только слова Линдона, - просто слова, наименьшие в классе сорпряженности. Всего-то надо добавить слова-степени тех линдоновских, кто по размеру есть делителем указаной(макс.) длины.
Для простых длин таких слов не будет. Да и опыт генерации подсказывает, что лишняя работа при генерации будет только для нечётных "порядков" слов.. а при чётных словах последнее валидное - почти в конце. Те дополнительные, непримитвы, как правило, стоят существенно дальше по порядку. Они немного портят картину, но деваться некуда.

[Mihaylo]

Вы уж определитесь, какую задачу решаете. В начале одно, в конце другое. Точную постановку задачи вы дали в начале. И в итоге я запомнил лишь выделенное жирным шрифтом. Исправьтесь, пожалуйста.

[Nartu]

Ладно. Вот вам чистая задача без моих предложений, полученых результатов, а так же без обобщений задачи.

Найдите эффективный алгоритм генерации всех слов длины \textstyle{n}$ с над упорядоченым алфавитом из двух символов, таких, что имеют постоянное число букв каждого вида, заданое как пара $\textstyle{m,k\in\mathbb{N} : m+k=n}$ $\phantom{x}$и лексически меньше всех своих сопряженных(цикл.перестановок).

Стартовое сообщение составлял около двух часов) Только в конце заметил, что мне для удобства лучше делать слова с правосторонним порядком, не $\textstyle{00001}$, а $\textstyle{10000}$. Но это вообще не влияет особо, просто что бы поняли, почему мои результаты перевёрнуты.

[Утундрий]

Nartu в сообщении #1580817 писал(а):

меньше всех своих сопряженных.

Что здесь означает "меньше"?

[Nartu]

отредактировал теперь правильно

[Mihaylo]

Надо бы попробовать прикрутить динамическое программирование к задаче...
Конкатенация двух слов Линдона к чему приводит? Случайно не оказывается, что достаточно проверить четыре или два варианта (мало вариантов), чтобы найти правильную перестановку? Есть какие-то теоремы на счёт наращивания слов Линдона?

-- 10.02.2023, 10:14 --

Теорема: при сложении двух слов Линдона $A$ и $B$ получается новое слово Линдона $AB$, если $A < B$ лексикографически. Без доказательства.

Элементарное слово Линдона - это слово, начинающееся нулями и заканчивающееся единицами, например, 01; 0001; 011; 00000111.

Для перехода к динамическому программированию нужно сделать так, чтобы к
ранее найденному слову с $(m-i)$ нулями и $(n-j)$ единицами можно было малозатратно подобрать всевозможные элементарные слова с $i$ нулями и $j$ единицами, которые лексикографически больше исходного слова...

[mihaild]

Mihaylo в сообщении #1580992 писал(а):

Теорема: при сложении двух слов Линдона $A$ и $B$ получается новое слово Линдона $AB$, если $A < B$ лексикографически.

Контрпример: $A = 01$, $B = 10$.

-- 10.02.2023, 11:05 --

А если просто сгенерировать все слова с нужным числом нулей, выкинуть периодические и из каждого взять лексикографически минимальный поворот? Мы тратим немного времени на генерацию периодических (но их мало по сравнению со всеми), и еще каждое слово генерируем по $n$ раз, но вроде разница между $C_n^k$ и $C_n^k / n$ не такая уж большая, так что это не сильно медленнее чем просто записать ответ.

[Mihaylo]

mihaild в сообщении #1581011 писал(а):

Контрпример: $A = 01$, $B = 10$.

$B = 10$ не является словом Линдона.

Однако 0; 00; 000; 0000 и т.д. являются словами Линдона. Но пусть в теореме будет оговорка "кроме нулевых слов Линдона".

[mihaild]

Mihaylo в сообщении #1581016 писал(а):

$B = 10$ не является словом Линдона.

Да, пардон, бред написал. Вроде правда, кроме случая $B = 0$.
$00$ и дальше словами Линдона тоже не являются (как и все периодические; иначе не будет единственности декомпозиции).

[Mihaylo]

Пытаюсь реализовать свой алгоритм. Понимаю, что я как нейросеть ChatGPT, пытаюсь максимально просто и быстро воссоздать видимые циклы, но как всегда есть ошибки, то забыл какой-то цикл, то забыл проверку условия, то цикл не включает начальный или конечный элемент, то наоборот имеет лишние элементы.

[Mihaylo]

Используется синтаксис Python

import time
start_time = time.time()
m = 5
k = 15
sample_words = [('', 0, 0, 0, 0)]
final_words = []
for word in sample_words: 
    for i in range(1, m - word[3] + 1):
        for j in range(1, k - word[4] + 1):
            if word[0] == '' or i < word[1] or (i == word[1] and j <= word[2]):
                new_word = word[0] + '0'*i + '1'*j
                if word[3] + i == m and word[4] + j == k:
                    final_words.append(new_word)
                else:
                    sample_words.append((new_word, i, j, word[3] + i, word[4] + j))
print("Сгенерировано %s слов Линдона за %s секунд." % (len(final_words), time.time() - start_time))
print(final_words)
 

-- 12.02.2023, 12:09 --

Это алгоритм генерации нетривиальных слов Линдона, когда $m \ne 0$, $k \ne 0$. Несложно доработать алгоритм, чтобы он умел генерировать тривиальные слова, когда $m = 0$ или $k = 0$.

-- 12.02.2023, 12:23 --

sample_word - это список слов Линдона с числом нулей и единиц меньшим, чем $m$ и $k$. Каждое слово сопровождается четырьмя вспомогательными характеристиками, для ускорения вычислений: число нулей и число единиц головного элементарного слова, число нулей и число единиц всего слова.
Головное элементарное слово - это то, что выделено жирным в примерах: 00000111010001, 010101.

-- 12.02.2023, 12:56 --

Извиняюсь, нашел в алгоритме ошибку, он генерирует не все слова Линдона. Но алгоритм корректный и очень быстрый. Просто я похоже нашел эвристику, которая позволяет не обходить дерево целиком.
Если развивать идею этого алгоритма и доводить решение до конца, то придется добавить цикл проверки слова на принадлежность к словам Линдона вместо этого простого условия:

Используется синтаксис Python

if word[0] == '' or i < word[1] or (i == word[1] and j <= word[2]):
 

Mihaylo в сообщении #1581236 писал(а):

число нулей и число единиц головного элементарного слова

И поправлюсь еще, здесь следовало написать "число нулей и число единиц последнего (хвостового) элементарного слова".

[Nartu]

Я не ожидал, что тема продолжится.. Но если тут начали составлять алгоритм для поиска слов конкретного числа "букв" нулей/единиц. То я должен напомнить, что есть алгоритм Дюваля для нахождения всех слов До заданой длины. Дюваль нашел метод создания лексически следующего слова. Он проходит в три этапа:

Выбираем какое-то слово Линдона, пусть $w=001$, бинарный алфавит.
1. Заполняем указаную максимальную длину ($\textstyle{n=5}$) буквами избранного слова (для $n$ будет $00100$);
2. Если заканчивается на любую букву кроме последней $\;-$ меняем её на следующую по алфавиту.
3. Если заканчивается на последнюю, то обрезаем ее и возвращаемся на п 2. до того момента, пока п. 2 не сработает( $n=6 : 001001 \to 00101$ )

Я работал именно с ним. И отталкивался от него. Сложность - линейная, а если работать с массивами, то может быть вообще $\operator{O}(1)$

Кажется, вот код, который я получил на Quora (на Python но я не питонист, уж извините):

def binary_lyndon_words(k, n): 
    # Make the array 1..n instead of 0..n-1, for each of comparison to the original 
    w = [None] + [0 for _ in range(n-k)] + [1 for _ in range(k)] 
    i = n 
    count = k 
    while i > 0: 
        for j in range(1, n-i+1): 
            count -= w[i+j] 
            count += w[j] 
            w[i+j] = w[j] 
        if i == n and count == k: 
            yield w[1:]  
        i = n 
        while i > 0 and w[i] == 1: 
            i = i - 1 
        if i > 0: 
            count += 1 
            w[i] = w[i] + 1 

Примеры

>>> list( binary_lyndon_words( 3, 8) ) 
[[0, 0, 0, 0, 0, 1, 1, 1],  
 [0, 0, 0, 0, 1, 0, 1, 1],  
 [0, 0, 0, 0, 1, 1, 0, 1],  
 [0, 0, 0, 1, 0, 0, 1, 1],  
 [0, 0, 0, 1, 0, 1, 0, 1],  
 [0, 0, 0, 1, 1, 0, 0, 1],  
 [0, 0, 1, 0, 0, 1, 0, 1]] 
>>> sum( 1 for _ in binary_lyndon_words( 6, 24)) 
5598 
>>> sum( 1 for _ in binary_lyndon_words( 8, 32)) 
876525  # but takes too long 

Могу дать ссылку на источник, там расписано, но... Quora любит рекламу...