Удвоение в конечных последовательностях

[maxal]

lofar писал(а):

Эта задача имеет непосредственное отношение к теории полугрупп. "Элементы перестановки" --- порождающие свободной полугруппы (полугруппы слов); "последовательности" --- элементы свободной полугруппы (слова); "удвоения" --- квадраты; последовательности без "удвоений" --- бесквадратные слова. Полагаю, что для поиска решения (если оно есть) нужно использовать эти ключевые слова.

Не возражаю, если это хоть сколько-нибудь поможет продвинуться в решении.
Обращаю внимание на следующие важные моменты:
1. начальное слово является перестановкой букв алфавита (то есть каждая буква в нем встречается ровно один раз);
2. найти нужно любую последовательность удвоений (их может быть несколько, это ничему не противоречит), переводящую начальную перестановку в данное слово.

Добавлено спустя 4 минуты 58 секунд:

Батороев писал(а):

А что мешает проверить заданную последовательность на "ненарушаемое" повторение?
В Вашем примере: 1,2,3,2,1,2,3,2,3,4,5 повторяются без нарушений:1, 2, 3, 2. Следовательно, это последнее повторение. Вырежем его.
Получим:1,2,3,2,3,4,5. Здесь ненарушаемое повторение: 2, 3 - это предпоследнее. Вновь вырезаем.
Получаем: 1, 2, 3, 4, 5. Повторений нет.

А что в случае, если есть несколько перекрывающихся "ненарушаемых повторений" - какое из них выбрать?

P.S. В этой задаче можно сходу придумать несколько эвристик, но вопрос ставится о точном решении. Если вы предлагаете алгоритм, будьте добры доказать его корректность.

[Руст]

На денёк остался без интернета. Подключаюсь к обсуждению опять.
Как правильно заметил lofar, алгоритм (предлагаемый Батороевым), основанный на сокращении удвоений (действующий в обратном направлении) может застопорится не на исходной последовательности. Здесь мы имеем дело не с эквивалентностями слов а о направленных преобразований удвоениями A --> B.
В общем задача оказалась не простой. В том, что я предлагал, так же много вопросов. Сходу все вопросы не решить. Этим можно заниматься разве что за оплату.

[Батороев]

"Утро вечера мудренее".
Посмотрел пример LOFAR'a и склонился к мысли, что "миссия не выполнима"...
Если с его примером, с грехом пополам, еще можно справиться, имея в виду, что часть повторения: $ ab-ab $ является элементом повторения $ babc-babc $, то уж в примере:
$ abababc $ невозможно узнать наверняка, что является последним повторением: то ли $ ab-ab $, то ли $ ba-ba $.

Такая путаница может привести к совершенно неправильным выводам биологов.
А их ошибки могут быть непоправимы

[bot]

Что-то я не вникаю в задачу. Удваивать через букву нельзя? То есть, как говорит lofar речь идёт о свободной идемпотентной полугруппе?
Если так, то уже для двух переменных ни из ab ни из ba удвоением не получится aba - это просто разные элементы этой полугруппы.
P.S. В этой полугруппе 6 элементов: a, b, ab, ba, aba, bab.

[lofar]

bot писал(а):

Что-то я не вникаю в задачу...

Приведу алгебраическую формулировку задачи (как это понял я).

Имеется свободная конечнопорожденная полугруппа $U=[a_1,\ldots, a_n>$. Определено отношение редукции $\rightarrow$: для любых слов $x,y\in U$ пишем $x\rightarrow y$ если найдутся $u,v,w\in U$ такие, что $x=uvvw$ и $y=uvw$. Задача состоит в том, чтобы по заданному слову $x\in U$ определить существует ли последовательность редукций $x=x_0\rightarrow x_1\rightarrow\ldots\rightarrow x_k=y$ такая, что в $y$ все буквы различны. И если она существует, то найти ее.

Конечно, транзитивное симметричное замыкание отношения $\rightarrow$ (обозначим его $\sim$) является конгруэнцией и $U/\sim$ есть свободная $n$-порожденная идемпотентная полугруппа (СИП). Другое дело, что в задаче рассматривается только транзитивное замыкание $\rightarrow$, и, стало быть, эта задача не эквивалентна проблеме тождества в СИП.

Отношение $\rightarrow$ удовлетворяет условию обрыва убывающих цепочек (меньшим считаем элемент на конце стрелки) и следовательно набор описанных редукций образует схему симплификации на $U$. Вместе с тем, эта схема не обладает свойством канонизации, так как для нее не выполняется условие локального слияния (что я продемонстрировал в предыдущем сообщении).

Задача, разумеется, алгоритмически разрешима. Достаточно рассмотреть все возможные способы редуцирования (их конечное число). Вместе с тем, сложность этого наивного алгоритма равна $O(2^{N^2})$ ($N$ --- длина исходного слова).

[Руст]

lofar писал(а):

1. И если она существует, то найти ее.

2. Задача, разумеется, алгоритмически разрешима. Достаточно рассмотреть все возможные способы редуцирования (их конечное число). Вместе с тем, сложность этого наивного алгоритма равна $O(2^{N^2})$ ($N$ --- длина исходного слова).

1. Если существует, то она находится тривиально, как говорилось раньше.
2. Вы учли, что после редукции могут появится новые редукции не существовавшие до неё.
Поэтому грубая оценка ещё выше.

[lofar]

lofar писал(а):

И если она существует, то найти ее

Здесь имется в виду последовательность редукций (ее надо отыскать).

Руст писал(а):

Вы учли, что после редукции могут появится новые редукции не существовавшие до неё.
Поэтому грубая оценка ещё выше.

Моя оценка ($O(2^{N^2})$) совсем грубая. Я исходил из того, что
1) Каждая цепочка редукций состоит не более чем из $N$ звеньев.
2) Число всех подслов в слове длины $K$ не превосходит $K^2$.

[Руст]

Как уже говорилось редукций может быть много. И целью являлось хотя бы одну.
То, что количество подслов порядка K^2 относится только к словам из последовательных букв. Как было замечено, в последующим могут сокращаться слова, у которых до начальной редукции буквы не шли подряд. Поэтому, я и спрашивал, учли ли вы это.
На самом деле получается более точная верхняя оценка таким образом. Пусть f(n) означает максимально возможное количество возможных редукций в слове длины n. Очевидно, что
f(1)=0,f(2)=1 и
$f(n)=\sum_{k=1}^{[n/2]}(n-k)f(n-k)$.
Рекурентное соотношение упрощается до:
$f(2k)=2kf(2k-1), \ f(2k+1)=(2k+1)f(2k)-kf(k).$
На самом деле f(n) совпадает с количеством редукций для слов из одной буквы и растёт чуть медленнее n! и быcтрее (n-1)!, точнее f(n)/n! имеет ненулевой предел примерно равный 0.315.

[lofar]

Руст писал(а):

$f(n)=\sum_{k=1}^{[n/2]}(n-k)f(n-k)$.

Простите, а разве не так должно быть:

$$f(n)=\sum_{k=1}^{[n/2]}(n-2k+1)f(n-k)$$

?

[Руст]

Нет сокращается на длину k, соответственно, количество мест сокращения n-k.

[lofar]

Руст писал(а):

Нет сокращается на длину k, соответственно, количество мест сокращения n-k.

Да, поэтому $\ldots f(n-k)$, но ведь в слове длины $n$ имеется ровно $n-2k+1$ подслов длины $2k$.

[Руст]

Да, вы правы. Только это существенно не улучшает. Оценка всё равно останется с факториальным ростом, только коэффициент перед факториалом (предельное значение) будет чуть меньше.

[juna]

Извините за вмешательство (и потенциально глупый вопрос), к сожалению, у меня мало времени, но при ответе на п. 1 задания maxal, разве можно как-то по указанным правилам получить последовательность $\{1221\}$ из перестановки $\{12\}$? Или же вопрос ставится - какие можно получить, а какие нельзя?

[Руст]

Артамонов Ю.Н. писал(а):

Извините за вмешательство (и потенциально глупый вопрос), к сожалению, у меня мало времени, но при ответе на п. 1 задания maxal, разве можно как-то по указанным правилам получить последовательность $\{1221\}$ из перестановки $\{12\}$? Или же вопрос ставится - какие можно получить, а какие нельзя?

Конечно нет.
Вопрос ставится, как определить можно ли получить. Если можно, то указать хотя бы один из способов получения.
Я до сих пор уверен, что мой способ отвечает на вопрос за полиномиальное время. Только из-за длинности описания и недоработанности некоторых деталей мне лень описать свой алгоритм.

[Macavity]

Артамонов Ю.Н. писал(а):

Извините за вмешательство (и потенциально глупый вопрос), к сожалению, у меня мало времени, но при ответе на п. 1 задания maxal, разве можно как-то по указанным правилам получить последовательность $\{1221\}$ из перестановки $\{12\}$?

Да, конечно, нельзя. Это один из инвариантов удвоения - "левый" порядок цифр, всегда такой же как и "правый" после каждого удвоения.

Например - последовательность 1,2,3,2,1,4,5,3,2,5,4,2,2,4
"левый" порядок - 1,2,3,2,1,4,5,3,2,5,4,2,2,4
"правый" порядок - 1,2,3,2,1,4,5,3,2,5,4,2,2,4
Поскольку "левый" и "правый" порядки не совпадают, то это значит, что такая последовательность удвоением не может быть получена.

Обратное, вообще говоря, неверно.
Последовательность 1,2,3,2,1,2,3,2,3,4,5 имеет одинаковые "левый" и "правый" порядки - 1, 2, 3, 4, 5. И последовательность может быть получена удвоением.

А следующий пример - 1,2,3,1,3,2,3. Порядки одинаковые, а получить цепочку удвоением нельзя.

Хотя правило удвоения достаточно общее - то что может быть получено утроением, учетверением и т.д. может быть получено и удвоением . Но есть правила, соответствующие этому инварианту, но не являющиеся удвоением. А вообще, это все напоминает отдаленно контекстно свободные грамматики...