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

[maxal]

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

Пусть нам изначально дана некоторая последовательность чисел $\{1,2,\dots,n\}$ без повторений (то есть, перестановка). Над ней несколько раз производится следующая операция: берется некоторый отрезок последовательности и удваивается. Например, начав с тождественной перестановки для n=5:
1, 2, 3, 4, 5
можно получить
1, 2, 3, 2, 3, 4, 5 (удвоили отрезок 2,3)
1, 2, 3, 2, 3, 4, 5, 3, 2, 3, 4, 5 (удвоили отрезок 3,2,3,4,5)
и так далее.

Пусть теперь нам дана некоторая конечная последовательность чисел $\{1,2,\dots,n\},$ где каждое число присутствует хотя бы один раз и, возможно, с повторениями. Вопросы:

1) Можно ли данную последовательность получить указанным выше образом из какой-то перестановки чисел $\{1,2,\dots,n\}$?
Замечание. Понятно, что, если это так, то начальная перестановка находится однозначно: достаточно из данной последовательности выделить первое вхождение каждого числа от 1 до n - это и будет начальная перестановка.

2) Если ответ на вопрос 1 утвердительный, нужно найти последовательность удвоений, преобразующих начальную перестановку к данной последовательности.

3) Определить алгоритмическую сложность предыдущих вопросов (полиномиальная, NP-полная и т.п.)

Какие будут идеи по поводу решения этой задачи?

[Руст]

maxal писал(а):

1) Можно ли данную последовательность получить указанным выше образом из какой-то перестановки чисел $\{1,2,\dots,n\}$?
Замечание. Понятно, что, если это так, то начальная перестановка находится однозначно: достаточно из данной последовательности выделить первое вхождение каждого числа от 1 до n - это и будет начальная перестановка.

2) Если ответ на вопрос 1 утвердительный, нужно найти последовательность удвоений, преобразующих начальную перестановку к данной последовательности.

3) Определить алгоритмическую сложность предыдущих вопросов (полиномиальная, NP-полная и т.п.)

Какие будут идеи по поводу решения этой задачи?

Ясно, что последовательность удвоений не восстанавливается. Например если удваивается некоторая последовательность символов А-->AA, потом удваивается последовательность B, содержащая АА получается CAADCAAD, то эта же последовательность может быть получена из CAD удвоением CADCAD, а потом удвоением А дважды. Даже места удвоений не восстанавливается, например пусть последовательность A разбита на две подпоследовательности A=BC, после удвоения А получаем AA, если удвоем любую подпоследовательность АА с длиной А получим ААА не важно с какого места начали, действительно АА=BCBC удваивая СB (последовательность с длиной А) получим опять
B CBCB C=AAA. Т.е. в общем случае не восстанавливается ни количество удваиваний ни места удваиваний.
Алгоритм, отвечающий на первый вопрос и дающий некоторую, вообще говоря не совпадающую с исходной последовательность удваиваний легко построить и он полиномиальный по длине.

[maxal]

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

Алгоритм, отвечающий на первый вопрос и дающий некоторую, вообще говоря не совпадающую с исходной последовательность удваиваний легко построить и он полиномиальный по длине.

Прошу предъявить алгоритм.

[Руст]

Построение алгоритма фактический школьная задача.
Приведу одно необходимое (возможно и достаточное условие) возможности получения от некоторой перестановки. Вообще элементы можно нумеровать так, что исходную последовательность можно считать 1,2,3,...,n (по порядку встречи). Тогда если последовательность $a_1,a_2,...,a_m$ получается из исходного, то она "непрерывна" снизу в том смысле, что $a_{i+1}\le a_i+1 \ \forall i<m$.
Там где нарушается естественный порядок, там было удвоение.

[maxal]

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

Построение алгоритма фактический школьная задача.
Приведу одно необходимое (возможно и достаточное условие) возможности получения от некоторой перестановки. Вообще элементы можно нумеровать так, что исходную последовательность можно считать 1,2,3,...,n (по порядку встречи). Тогда если последовательность $a_1,a_2,...,a_m$ получается из исходного, то она "непрерывна" снизу в том смысле, что $a_{i+1}\le a_i+1 \ \forall i<m$.
Там где нарушается естественный порядок, там было удвоение.

Но это же только начало. А как определить длину удвоения? Кроме того, это удвоение могло быть "старым" и уже перетерто "новыми". Например:
1,2,3,2,1,2,3,3,4,5
Здесь первое нарушение происходит при i=3, но сразу восстановить удвоение в этой позиции не получится.

[Руст]

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

[maxal]

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

Места, количество и длины удвоений как уже было сказано не являются инвариантами. Главное выяснить можно получить данную последовательность из исходного или нет, если можно, то дать хоть какой нибудь способ получения.
Приведенная тобою последовательность не является таковой

Я описался в той воследовательности. Имелась в виду такая:
1,2,3,4,5
1,2,3,2,3,4,5 (удвоили 2,3)
1,2,3,2,1,2,3,2,3,4,5 (удвоили 1,2,3,2)

[Руст]

Я то же имел в виду это, сравннивая с тем, что не может быть получена.

[maxal]

Ну так для
1,2,3,2,1,2,3,2,3,4,5
пресловутое условие нарушается для i=3, но удвоения с этой позиции не найти

[Руст]

Это означает, что в этом месте было удвоение длины минимум 2, т.е. (2,3). Минимально возможная длина удвоения $h=a_i+1-a_{i+1}$. Везде h не отрицательная величина, там где h положителен, там было удвоение длины не меньше h.
Как выяснилось, "непрерывность снизу" является только необходимым, а не достаточным условием. Необходимо так же связь суммы h с удлинением.

[maxal]

Я все равно не вижу, почему алгоритм получается полиномиальный.

[Руст]

Находим первое нарушение, в нашем примере. Вычислили h=2, соответственно здесь было удвоение (2,3) и последовательность предшествовал (1,2,3,2,3,4,5). Если не первое нарушение длина удвоения может быть больше и поэтому, надо искать ранние встречи $a_{i+1}$. Следующая опять нарушение и ранняя встреча 1 уже отстоит на 4, соответственно надо проверить является удвоением (1,2,3,2,1,2,3,2,3,4,5) совпало.
Количество удвоений не превосходит удлинения длины слова (линейно от длины). Каждое удвоение вычисляется линейно (в худшем случае квадратично) от длины. Следовательно, длина работы алгоритма квадратично (в худшем случае кубична).

[maxal]

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

Находим первое нарушение, в нашем примере. Вычислили h=2, соответственно здесь было удвоение (2,3) и последовательность предшествовал (1,2,3,2,3,4,5). Если не первое нарушение длина удвоения может быть больше и поэтому, надо искать ранние встречи $a_{i+1}$. Следующая опять нарушение и ранняя встреча 1 уже отстоит на 4, соответственно надо проверить является удвоением (1,2,3,2,1,2,3,2,3,4,5) совпало.

А как доказать корректность этого алгоритма? Почему, например, откат первого найденного "возможного" удвоения приведет в нужному результату? Кроме того, в одной и той позиции может начинаться удвоения разной длины - какое их них предпочесть и почему?

[Батороев]

А что мешает проверить заданную последовательность на "ненарушаемое" повторение?
В Вашем примере: 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.1 Вышеуказанное справедливо, если я правильно понял алгоритм удвоения, что повторенная часть вставляется рядом.
p.s. 2 Проверять необходимо всю последовательность, только после чего можно делать вывод о "ненарушаемых" повторениях. Например, в последовательности
1, 2, 1, 2, 3, 4, 5, 1, 2, 1, 2, 3, 4, 5 последнее повторение: 1, 2, 1, 2, 3, 4, 5, а не 1, 2.
Т.е. необходимо проверить, не являются ли встречающиеся повторения частями другого большего повторения.

[lofar]

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

В случае если основной алфавит содержит более двух символов, предлагаемый Руст алгоритм редуцирования удвоений работает не всегда. Например, слово $ababcbabc$ можно получить из $abc$: $abc\rightarrow ababc\rightarrow ababcbabc$. Вместе с тем, алгоритм редуцирования может привести и к другому (отличному от $abc$) бесквадратному слову: $ababcbabc\rightarrow abcbabc$.