Восстановление последовательности

 
0
 
Algorithmen
ava
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 всевозможных сдвигов)
Потом берем все последовательности и сортируем в лексикографичесокм порядке и берем их последние элементы
Получаем новую последовательность, по ней надо восстановить исходную.

Помогут любые дельные идеи, реализую уже я их сам. 
Kommentare (11)
ava
Akina | 28.10.2016, 18:42 #
Цитата (urdnot @  28.10.2016,  19:06 findReferencedText)
Потом сортируем эти сдвиги лексикографически и берем последние элементы, получаем некую перестановку начальной последовательности.

А есть доказательство этого утверждения?
ava
urdnot | 28.10.2016, 18:50 #
Цитата (Akina @  28.10.2016,  18:42 findReferencedText)
А есть доказательство этого утверждения? 


Наверное я не совсем понятно объяснил про сдвиги. Это все возможные вращения последовательности , например:
{3,5,6,1} ->  {5,6,1,3}
                      {6,1,3,5}
                      {1,3,5,6}
                      {3,5,6,1}
Поэтому на последней позиции окажутся все элементы последовательности, а лексикографическая сортировка перемешает их, т.е. получится перестановка исходной последовательности какая-то
ava
Akina | 28.10.2016, 18:53 #
Ааа... ок.
Нада подумать... как я понимаю, полный перебор тебя не устроит.
ava
urdnot | 28.10.2016, 19:03 #
Цитата (Akina @  28.10.2016,  18:53 findReferencedText)
как я понимаю, полный перебор тебя не устроит. 

Мне нужно зарешать ее для конкретного теста и в нем 6500 чисел, т.е. перебор вообще никак. У меня есть некоторые мысли по задаче , вот мы знаем что последовательность это последние элементы отсортированной последовательности, и их первые элементы получается это отсортированная исходная последовательность т.е. у нас уже получается первые и последние элементы. Например если бы на вход подвалась последовательность из различных элементов без повторений по этим парам мы бы просто восстановили исходную последовательность, но они ж повторяться могут.
ava
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}
Дальше проделываем тоже самое и получаем нужную последовательность с точность до поворота (этого достаточно)

Но вот в усложненном варианте такой подход не дает нужный результат.
ava
Akina | 28.10.2016, 20:36 #
Цитата (urdnot @  28.10.2016,  20:03 findReferencedText)
перебор вообще никак

Тогда обрати внимание на то, что последовтельность, отвечающая исходным условиям, состоит из группы подпоследовательностей, каждая их которых лексикографически больше и не длиннее предыдущей, а её элементы образуют неубывающую последовательность. В твоём примере это три подпоследовательности {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 вариантов перебрать... а всего вариантов будет порядка сотни.

später ergänzt:
Цитата (urdnot @  28.10.2016,  20:57 findReferencedText)
исходная последовательность: {3,3,6,3,3} разобьется на {{3,3,6}, {3}, {3}}

Или {{3,3,6}, {3,3}}.
ava
urdnot | 28.10.2016, 20:50 #
Цитата (Akina @  28.10.2016,  20:36 findReferencedText)
обрати внимание на то, что последовтельность, отвечающая исходным условиям, состоит из группы подпоследовательностей, каждая их которых лексикографически больше и не длиннее предыдущей, а её элементы образуют неубывающую последовательность

Можно придумать последовательность которая не будет этому удовлетворять: 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}
ava
urdnot | 28.10.2016, 21:19 #
Цитата (Akina @  28.10.2016,  20:36 findReferencedText)
В твоём примере: конечный набор состоит из чисел 99, 10, 11, 3, 3, 3, 6, 6, 6}.

Если подпоследовательность одна - это 3,3,3,6,6,6,10,11,99.

(*) {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
ava
Akina | 28.10.2016, 21:23 #
Цитата (urdnot @  28.10.2016,  21:50 findReferencedText)
{3,3} не удовлетворяет потому что ее суффикс {3} меньше ее самой. {3} < {3,3}

Про суффикс суффикса речи нигде не было...
ava
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}}
ava
urdnot | 28.10.2016, 22:51 #
Понял как решать усложненную задачу , если тебе интересно позже опишу алгоритм.
Registrieren Sie sich oder melden Sie sich an, um schreiben zu können.
Unternehmen des Tages
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Mitwirkende
  Akina   urdnot
advanced
Absenden