Суперпоследовательность s последовательности p — такая последовательность, множество подпоследовательностей которой содержит, среди прочего, все перестановки последовательности p.
Пример:
Чтобы далее не заморачиваться с наборами неуникальных элементов, будем полагать, что p(n) = [1..n], т.е. алфавит из n букв.
Напишите:
1) Предикат, проверяющий, является ли данная строка s суперпоследовательностью для алфавита p(n). Наивная реализация занимает O(n! * length(s)), это неприемлемо долго.
2) Генератор кратчайшей суперпоследовательности для p(n)
3) Формулы для оценки нижней и верхней границ её длины. Понятно, что грубые оценки — это n и n^2-n+1. Можно ли их сузить?
4) Формулы для оценки количества кратчайших суперпоследовательностей.
Для любителей самообразования:
— напишите это на Хаскелле и на J
— — наиболее читаемо
— — наиболее компактно
— — наиболее быстродействующе
К>Суперпоследовательность s последовательности p — такая последовательность, множество подпоследовательностей которой содержит, среди прочего, все перестановки последовательности p. К>Пример: К>[code] К>p = 1 2 3 К>s = 1 2 3 1 2 3 1
Сорри, не понял, а где в s подпоследовательность "321"?
К>4) Формулы для оценки количества кратчайших суперпоследовательностей.
Оценка сверху -- О(n^2 — n + 1)
Видно уже из приведенного вами примера.
Как строго доказать пока не знаю.
Пока проба.
У нас есть ровно n-1 последовательностей.
В них можно набрать любую последовательность из n чисел кроме n, n-1, ... , 1
Поэтому добавляем единичку в конец.
Здравствуйте, Zuka, Вы писали:
Z>Здравствуйте, Zuka, Вы писали:
Z>>Здравствуйте, Кодт, Вы писали:
Z>>Есть подозрение, что оценка снизу 2^n — 1.
Z>В том что оценка сверху равна 2^n — 1 я уже кажется могу доказать....
То, что оценка сверху 2^n-1 верна, доказать несложно.
Есть элегантный способ построения суперпоследовательностей.
Если нам надо суперпоследовательность для n, то мы ставим суперпоследовательность для n-1, затем число n, а затем опять любую суперпоследовательность для n-1. Получим суперпоследовательность для n.
Т.е. если для n-1 длина суперпоследовательности не больше 2^(n-1)-1, то для n она на больше, чем 2*(2^(n-1)-1)+1 = 2^n-1. Кроме того, для n=2 или 3 эта оценка работает.
Проблема, однако в том, что такая суперпоследовательность будет заведомо длиннее, чем та, что имеет длину n^2-n+1 при n>3, а для n=2,3 они совпадают. Так что, такая оценка не очень помогает в данном случае.
Здравствуйте, Кодт, Вы писали:
К>Напишите: К>2) Генератор кратчайшей суперпоследовательности для p(n) К>3) Формулы для оценки нижней и верхней границ её длины. Понятно, что грубые оценки — это n и n^2-n+1. Можно ли их сузить? К>4) Формулы для оценки количества кратчайших суперпоследовательностей.
Суперпоследовательность 1..n...(n-1)...1..n1 явно подходит. Это означает, что оценка сверху n^2-n+1. Это то, что Кодт назвал грубой оценкой сверху.
Грубая снизу n также очевидна. Более того, очевидна грубая оценка снизу 2n-1, так как где-то в суперпоследовательности должны быть последовательности 1..n и n..1.
Для n=2 две оценки совпадают и дают длину суперпоследовательности 3. Значит, какие бы другие формулы для оценок мы тут ни придумали, они должны стартовать с 3 (для n=2).
Далее, на счет числа таких суперпоследовательностей. Возьмем любую из них, перенумеруем все числа в произвольном порядке. Получим опять суперпоследовательность. Т.е. их число делится на n!. Чтобы избежать этих трудностей назовем суперпоследовательностью в канонической форме минимальную суперпоследовательность, у которой первая подпоследовательность, состоящая из n различных чисел, равна 1..n. Очевидно, что каноническая суперпоследовательность должна начинаться с 12. Всюду далее, опять таки для простоты, будем избегать употребления слова каноническая. И будем считать теперь число (канонических) суперпоследовательностей.
Для n=1. 1
Итого: 1 суперпоследовательность длины 1.
Для n=2 она одна. 121
Итого: 1 суперпоследовательность длины 3.
Для n=3 грубые оценки дают 5 и 7. Построим суперпоследовательность. 12*3*2*1* (где * означает 0 или более цифр) Чего не хватает: 213, 312. Нужно две добавить. Варианты 1213212, 1213121, 1231321, 1231231, 1231213, 1232132 и 1232123. 7 вариантов, если не ошибся. Всего будет 7*3!=42 минимальные суперпоследовательности (не обязательно канонические).
Итого: 7 суперпоследовательностей длины 7.
1213121
1213212
1231213
1231231
1231321
1232123
1232132
Для n=4 уже немного сложнее. Надо бы набросать программку, пусть даже неоптимальную.
Итого: 9 суперпоследовательностей длины 12 (оценки 7<= <=13).
123412314213
123412314231
123412314321
123413214231
123413214312
123413214321
123421324123
123421324132
123421324312
Здравствуйте, Кодт, Вы писали:
К>Суперпоследовательность s последовательности p — такая последовательность, множество подпоследовательностей которой содержит, среди прочего, все перестановки последовательности p.
Пара вопросов на засыпку:
1) Для n<=4 были найдены все минимальные суперпоследовательности. Во всех случаях была хотя бы одна последовательность, начинающаяся на 12..n, и заканчивающаяся на n..21. Верно ли, что это всегда так?
2) Ясно, что ни одна минимальная суперпоследовательность не может содержать две подряд идущие одинаковые цифры aa. Однако она может содержать abcabc (пример при n=3: 1231231). Может ли она содержать abab?
К>Суперпоследовательность s последовательности p — такая последовательность, множество подпоследовательностей которой содержит, среди прочего, все перестановки последовательности p.
К>Напишите: К>1) Предикат, проверяющий, является ли данная строка s суперпоследовательностью для алфавита p(n). Наивная реализация занимает O(n! * length(s)), это неприемлемо долго. К>2) Генератор кратчайшей суперпоследовательности для p(n) К>3) Формулы для оценки нижней и верхней границ её длины. Понятно, что грубые оценки — это n и n^2-n+1. Можно ли их сузить? К>4) Формулы для оценки количества кратчайших суперпоследовательностей.
Вот последние результаты (посчиталось для n=5):
Как я раньше уже написал, будем рассматривать только канонические суперпоследовательности -- минимальные суперпоследовательности, у которых первая встречающаяся перестановка из n различных чисел равна 1..n.
Пусть Kn -- число канонических суперпоследовательностей, тогда общее число суперпоследовательностей равно Kn*n!.
Пусть Ln -- длина минимальной суперпоследовательности.
Вот что у нас есть:
n Kn Ln оценки снизу и сверху
1 1 1 1 1
2 1 3 3 3
3 7 7 5 7
4 9 12 7 13
5 128 19 9 21
Ln близко к верхней оценке, но меньше.
Еще парочка наблюдений (по поводу двух вопросов заданных мной ранее).
Другая моя программка ищет (и делает это намного быстрее) минимальные суперпоследовательности, которые начинаются с 1..n и заканчивабтся на n..1 (была гипотеза, что такая минимальная суперпоследовательность всегда есть). Так вот, для n=5 минимальная такая суперпоследовательность имеет длину 20, т.е. не является минимальной среди всех суперпоследовательностей. Т.е. ответ на один из вопросов отрицательный. Уже для n=5 нет минимальных суперпоследовательностей, начинающихся на 1..5, и заканчивающихся на 5..1.
Среди всех 128 минимальных суперпоследовательностей по прежнему нет ни одной, содержащей abab. Т.е. этот вопрос остается пока открытым (это сущесвенно сократило бы перебор).
Забавно также, что, как и для n=4, для n=5 все суперпоследовательности начинаются на 1..n. Единственное (пока) n, для которого это не так -- n=3 (для n=3 среди 7 суперпоследовательностей 5 только начинаются на 123).
Здравствуйте, Кодт, Вы писали:
К>Суперпоследовательность s последовательности p — такая последовательность, множество подпоследовательностей которой содержит, среди прочего, все перестановки последовательности p.
К>Напишите: К>1) Предикат, проверяющий, является ли данная строка s суперпоследовательностью для алфавита p(n). Наивная реализация занимает O(n! * length(s)), это неприемлемо долго. К>2) Генератор кратчайшей суперпоследовательности для p(n) К>3) Формулы для оценки нижней и верхней границ её длины. Понятно, что грубые оценки — это n и n^2-n+1. Можно ли их сузить? К>4) Формулы для оценки количества кратчайших суперпоследовательностей.
Принимаюсь за перебор для n=6. По моим подсчетам это займет не более 10000 лет...
Ок, допустим, для n=6 такая последовательность годится. Ее длина 28.
Но есть ли гарантия, что нет последовательности меньшей длины?
Или то, что ты имеешь в виду, это, что если найдены хотя бы по одной, то верны новые оценки, данные сверху?
известно:
7 вместо 7 (-0)
12 вместо 13 (-1)
19 вместо 21 (-2)
гипотеза:
28 вместо 31 (-3)
39 вместо 43 (-4)
52 вместо 57 (-5)
Она подкрепляется найденными последовательностями.
Это здорово, но нет гарантии, что эти самые минусы в скобках растут линейно. Т.е. нет гарантии, что, например, для n=7 нет последовательности длины 38 (-5), например.
Может там что-то более сложное. Ведь для n=1,2,3 было (-0). А потом, когда стало достаточно цифр для какой-то "внутренней оптимизации", мы стали отходить от верхней границы. Линейно пока. Может после еще пары цифр мы начнем отходить от нее быстрее?
Кстати, там по ссылке никаких ответов нет?
P.S. Подумайте, плиз, насчет abab. Это может помочь. Например, до того, как я убрал последовательности с aa, алгоритм n=5 тоже не осиливал. А потом, как убрал, стал.
Здравствуйте, vadimcher, Вы писали:
V>P.S. Подумайте, плиз, насчет abab. Это может помочь. Например, до того, как я убрал последовательности с aa, алгоритм n=5 тоже не осиливал. А потом, как убрал, стал.
Не должно быть abab.
Пусть есть abab, меняем на aba, ничего не меняется.
Т.к. любая подпоследовательность-перестановка пересекается с abab максимум в одной a и одной b, как бы это не происходило всегда можно обойтись только первой b.
Здравствуйте, Иванков Дмитрий, Вы писали:
ИД>Здравствуйте, vadimcher, Вы писали:
V>>P.S. Подумайте, плиз, насчет abab. Это может помочь. Например, до того, как я убрал последовательности с aa, алгоритм n=5 тоже не осиливал. А потом, как убрал, стал.
ИД>Не должно быть abab. ИД>Пусть есть abab, меняем на aba, ничего не меняется. ИД>Т.к. любая подпоследовательность-перестановка пересекается с abab максимум в одной a и одной b, как бы это не происходило всегда можно обойтись только первой b.
Спасибо.
Честно говоря, я сам как-то не успел подумать, просто для aa это очевидно, а abcabc я увидел в минимальной суперпоследовательности для n=3, вот и родился вопрос на счет abab, а оказалось достаточно легко убедиться, что и abab не может быть.
Я уже такие последовательности убрал (помогло, к сожалению, не так, как я надеялся -- когда я до этого убрал последовательности с aa помогло почему-то значительно заметнее).
Правда случай n=5 уже разрешен, а случаю n=6 уже ничто не поможет...
Здравствуйте, vadimcher, Вы писали:
V>Принимаюсь за перебор для n=6. По моим подсчетам это займет не более 10000 лет...
Жаль что эту задачку все забросили потому, что перебор может быть очень сильно оптимизирован.
На ряду с исходной задачей рассмотрим задачу построения суперпоследовательностей для размещений из n по k. Для этой задачи у меня получилась оценка L(n,k)=L(k)+(n-k)*k (для n<=6 k<=5 проверено).
Теперь можно использовать эту оценку для решения исходной задачи следующим образом:
Пусть построено частичное решение длины m и имеется массив последовательностей которые которые еще осталось покрыть найдем такой набор размещений из p по q (перебор по сочетаниям из n по p) который собержится в этом массиве (как подпоследовательности отдельных элементов), тогда ясно что чтобы дополнить частичное решение до полного то придется по крайней мере покрыть эти размещения т.е. удлинить решение по крайней мере на L(p,q)+(n-p) ((n-p) цифр не попадут в покрытие).
Из этого следует что частичное решение должно удовлетворять условию m+L(p,q)+(n-p)<=L(n) если нет то продолжать его нет смысла. Это значительно сокращает перебор (построение всех суперпоследовательностей для n=5 занимает примерно 10 сек на моем лаптопе). Так что ждите, скоро n=6 падет.
Здравствуйте, vadimcher, Вы писали:
V>Принимаюсь за перебор для n=6. По моим подсчетам это займет не более 10000 лет...
Как обесчал n=6 сдалось
полное решение можно скачать эдесь http://ifolder.ru/2758902
есть неожиданости, например суперпоследовательность
0123425130243152034123501432
1. она не начинается на 012345
2. всего три 5-ки (против шести 2-ек)
3. очень маленькое расстояние между двумя первыми 2-ками (два против семи для 5-ок)
у меня складывается впечатление что для n=7 минимальная длина суперпоследовательности должна оказаться меньше ожидаемой 39
Перекуём баги на фичи!
Обязательно бахнем! И не раз. Весь мир в труху! Но потом. (ДМБ)
И будем считать теперь число (канонических) суперпоследовательностей.
