Цитата(urdnot @ 28.10.2016, 19:06  ) |
| Потом сортируем эти сдвиги лексикографически и берем последние элементы, получаем некую перестановку начальной последовательности. |
А есть доказательство этого утверждения?
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Восстановление последовательности |
| Автор: urdnot 28.10.2016, 18:06 |
| 1. Есть конечная последовательность натуральных чисел обладающая следующим свойством: (*) Любой суффикс этой последовательности лексикографически( только числа вместо букв) больше этой последовательности, например: a = {3, 6, 10, 3, 6, 11, 3, 6, 99}, какой суффикс ни возьми: 99 >a, {6, 99} > a, {3, 6, 99} > a, ... и т.д Потом мы берем и записываем все сдвиги этой последоваетльности т.е. {6,10,3,6,11,3,6,99,3}; {10,3,6,11,3,6,99,3,6}; ... и т.д Потом сортируем эти сдвиги лексикографически и берем последние элементы, получаем некую перестановку начальной последовательности. Для а ,например: {99, 10, 11, 3, 3, 3, 6, 6, 6} и вот надо воостановить по ней исходную последовательность. 2. Усложнение задачи 1. дана конечная последовательность натуральных чисел и мы слева направо начинаем искать максимальные подпоследовательности обладающие свойством (*) т.е. например: a = {3,56,78, 5,6,4,2,5,7,8,9,2,4,1} -> {{3,56,78,5,6,4}, {2,5,7,8,9},{2,4},{1}} Затем как в (1) для каждой подпоследовательности записываем все сдвиги (для посл. длин n , будет n всевозможных сдвигов) Потом берем все последовательности и сортируем в лексикографичесокм порядке и берем их последние элементы Получаем новую последовательность, по ней надо восстановить исходную. Помогут любые дельные идеи, реализую уже я их сам. |
| Автор: Akina 28.10.2016, 18:42 | ||
А есть доказательство этого утверждения? |
| Автор: urdnot 28.10.2016, 18:50 | ||
Наверное я не совсем понятно объяснил про сдвиги. Это все возможные вращения последовательности , например: {3,5,6,1} -> {5,6,1,3} {6,1,3,5} {1,3,5,6} {3,5,6,1} Поэтому на последней позиции окажутся все элементы последовательности, а лексикографическая сортировка перемешает их, т.е. получится перестановка исходной последовательности какая-то |
| Автор: Akina 28.10.2016, 18:53 |
| Ааа... ок. Нада подумать... как я понимаю, полный перебор тебя не устроит. |
| Автор: urdnot 28.10.2016, 19:03 | ||
Мне нужно зарешать ее для конкретного теста и в нем 6500 чисел, т.е. перебор вообще никак. У меня есть некоторые мысли по задаче , вот мы знаем что последовательность это последние элементы отсортированной последовательности, и их первые элементы получается это отсортированная исходная последовательность т.е. у нас уже получается первые и последние элементы. Например если бы на вход подвалась последовательность из различных элементов без повторений по этим парам мы бы просто восстановили исходную последовательность, но они ж повторяться могут. По подробнее распишу все же: 1. {3,5,6,2} 2. Повороты: {5,6,2,3} {6,2,3,5} {2,3,5,6} {3,5,6,2} 3. Сортировка: (*) {2,3,5,6} {3,5,6,2} {5,6,2,3} {6,2,3,5} 4. Последние элементы: {6, 2, 3, 5} (**) 5. Моя идея: мы знаем что (**) последние элементы (*) поэтому можеи воостановить частично (*) {2, ..., 6} {3, ... , 2} {5, ..., 3} {6, ..., 5} По этим парам {6,2} ,{2,3}, {3,5}, {5,6} можем восстановить исходную последовательность с точность до поворота ( в мое задаче этого достаточно, потом надо будет просто вращать пока не получишь минимальную последовательность) |
| Автор: urdnot 28.10.2016, 19:57 |
| Вот сейчас подумал, с небольшой можификацией моя идея решает 1ую задачу, например: a = {3,5,7,4,5,5} исходная последовательность (*) Отсортированные сдвиги (**): {3,5,7,4,5,5} {4,5,5,3,5,7} {5,3,5,7,4,5} {5,5,3,5,7,4} {5,7,4,5,5,3} {7,4,5,5,3,5} Последовательность по которой надо восстановить исходную {5,7,5,4,3,5} 1. {3,..., 5} -> {5, 3} (часть иходной последовательности) {4,...., 7} -> {7,4} {5,...., 5} - >{5, 5} {5, ..., 4} -> { 4,5} {5,..., 3} -> {3,5} {7, ..., 5} -> {5,7} Мы знаем что за 3 следует 5 (3 одна поэтому никаких проблем), за 4 следует 5 (тоже нет проблем), за 5 может идти 3,5,7 , но мы знаем что (**) отсортировано поэтому 3,5,7 сортируем и последовательновписываем после пятерок, с 7ой никактх проблемю Получаем: 2. {3, 5, ..., 5} - > {5,3,5} {4, 5, ...., 7} -> {7,4,5} {5, 3, ...., 5} - > {5,5,3} {5, 5, ...., 4} -> {4,5,5} {5, 7, ...., 3} -> {3,5,7} {7, 4, ...., 5} -> {5,7,4} Дальше проделываем тоже самое и получаем нужную последовательность с точность до поворота (этого достаточно) Но вот в усложненном варианте такой подход не дает нужный результат. Например исходная последовательность: {3,3,6,3,3} разобьется на {{3,3,6}, {3}, {3}} Затем после сдвигов и сортировок: {3} {3} {3,3,6} {3,6,3} {6,3,3} Получаем последовательность из последних элементов: {3,3,6,3,3} Получаем пары: {3, ... , 3} - {3, 3} ложная пара тройка зациклена на себе {3, ..., 3} - {3, 3} снова ложная {3, ..., 6} - {6,3} {3, ..., 3} - {3,3} {6, ...., 3} - {3, 6} {3, 3, ..., 3} - неверно {3, 3, ..., 3} - неверно {3, 3, ..., 6} {3, 6, ..., 3} {6,3, ..., 3} |
| Автор: Akina 28.10.2016, 20:36 | ||||
Тогда обрати внимание на то, что последовтельность, отвечающая исходным условиям, состоит из группы подпоследовательностей, каждая их которых лексикографически больше и не длиннее предыдущей, а её элементы образуют неубывающую последовательность. В твоём примере это три подпоследовательности {3,6,10},{3,6,11},{3,6,99}. В твоём примере: конечный набор состоит из чисел 99, 10, 11, 3, 3, 3, 6, 6, 6}. Если подпоследовательность одна - это 3,3,3,6,6,6,10,11,99. Если две - придётся рассматривать длины первой последовательности от 8 до 5. Для, скажем, 7, у нас возможны какие варианты? Для простоты рассмотрим вторую группу, из 2 элементов. Первый может быть 3,6,10 или 11. Он не может быть 99, т.к. тогда не найдём второго - ведь он должен быть не меньше. Если он 11, то второй - только 99. Если он 10, то второй 11 или 99. Если 6, то второй 6,10,11 или 99. Если 3, то второй 6,10,11 или 99 (3 быть не может, иначе не останется двух троек для первой группы). Т.е. всего-то 11 вариантов перебрать... а всего вариантов будет порядка сотни. Добавлено через 1 минуту и 27 секунд
Или {{3,3,6}, {3,3}}. |
| Автор: urdnot 28.10.2016, 20:50 | ||
Можно придумать последовательность которая не будет этому удовлетворять: a = {3,5, 90,85,83,82,81 /*убывает*/ , 50,51,52,53,54,55,56,57,58 /*длинее предыдущей*/} но тем не менее дуовлетворяет исходному условию: {58} > a, {57,58} >a, .., {83,82,...,58} > a, и т.д. Или я просто не правильно понял? Насчет {3,3,6,3,3} -> {{3,3,6},{3},{3}}. {3,3} не удовлетворяет потому что ее суффикс {3} меньше ее самой. {3} < {3,3} |
| Автор: urdnot 28.10.2016, 21:19 | ||
(*) {99, 10, 11, 3, 3, 3, 6, 6, 6} - это то что на вход подается, (**) {3,6,10,3,6,11,3,6,99} - это то что каким то образом надо восстановить (просто я знаю это потому что сам ее преобразовал и получил (*)). a = {3,6,10,3,6,11,3,6,99} - целиком удовлетворяет условию о суффиксах ее разбивать не нужно, т.е. {99} > a, {6,99} > a, {3,6,99} >a, {11,3,6,99} >a, {6,11,3,6,99} ,..., {6,10,3,6,11,3,6,99}>a. Точнее когда последовательность цеиком удовлетворяет условию о суффиксах, я понял как решать и выше написал, но вот когда последовательность нужно разбивать как с {3,3,6,3,3} там не понимаю как. |
| Автор: Akina 28.10.2016, 21:23 | ||
Про суффикс суффикса речи нигде не было... |
| Автор: urdnot 28.10.2016, 21:35 |
| Извини, я тебя запутал, {3,3,6,3,3} это я привел пример для 2ой усложненной задачи, там сперва последовательность бьется на максимальные части для которых верное условие с суффиксами (обозначю его (+)). т.е вот берем a = {3,3,6,3,3} возьмем а целиком для него (+) не выполнено потому что {3} < a, дальше берем {3,3,6,3} тоже не выполено {3} < {3,3,6,3}, далее {3,3,6} - выполнено: {6} > {3,3,6} ; {3,6} > {3,3,6} отделяем {3,3,6} от a, получаем {3,3,6} и остаток от а - {3,3}, для него проделываем тоже, проверяем целиком (+) - не выполнено т.к. {3} < {3,3}. Наконец берем {3} для нее (+) выполнено отделяем от {3,3} получаем остаток {3} и полностью {{3,3,6}, {3}, {3}} |
| Автор: urdnot 28.10.2016, 22:51 |
| Понял как решать усложненную задачу , если тебе интересно позже опишу алгоритм. |