2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 сортировка случайными вставками
Сообщение26.02.2009, 01:32 
Модератор
Аватара пользователя


11/01/06
5660
У Васи есть набор кубиков пронумерованных числами от $1,2,\dots,n$, которые выстоены в ряд в некотором порядке. Вася пытается расставить их в порядке возрастания номеров следующим образом. Найдя некоторый (произвольный) кубик, стоящий не на своем месте, он его вынимает и вставляет его на правильное место, сдвигая остальные кубики, не меняя порядка их следования. Сумеет ли Вася гарантированно закончить сортировку кубиков за конечное время?

(источник)

 Профиль  
                  
 
 
Сообщение26.02.2009, 02:20 
Заслуженный участник
Аватара пользователя


18/05/06
13435
с Территории
Сумеет, если характер его произволения таков, что за конечное время он наткнётся на первый кубик - ведь тот, будучи поставлен на правильное место, остаётся на нём и сводит задачу к $n-1$. (Или последний, то же самое).
А если нет, то нет.

 Профиль  
                  
 
 
Сообщение26.02.2009, 02:57 
Модератор
Аватара пользователя


11/01/06
5660
ИСН
Ответ неверный.
Возможно, вы не поняли вопрос. Переформулирую так: возможна ли ситуация, что Вася будет сортировать кубики бесконечно?

 Профиль  
                  
 
 
Сообщение26.02.2009, 03:20 


24/03/07
321
Сумма \sum_i|i-p(i)| не увеличивается, а оставлять её такой же бесконечно мы не сможем, т.к. если эта сумма не меняется, то растёт количество инверсий.

 Профиль  
                  
 
 
Сообщение26.02.2009, 03:36 
Модератор
Аватара пользователя


11/01/06
5660
Dandan писал(а):
Сумма \sum_i|i-p(i)| не увеличивается, а оставлять её такой же бесконечно мы не сможем, т.к. если эта сумма не меняется, то растёт количество инверсий.

Это неверно.
Например, в перестановке 42351 при перемещении 4 на свое место получается перестановка 23541 с тем же значением функции \sum_i|i-p(i)|, но меньшем числе инверсий.

 Профиль  
                  
 
 
Сообщение26.02.2009, 04:21 
Заслуженный участник


01/12/05
458
По-моему, ИСН все верно написал: если Вася выбирает кубик наудачу, то ему обязательно за конечное время попадется первый или последний.

 Профиль  
                  
 
 
Сообщение26.02.2009, 04:25 
Модератор
Аватара пользователя


11/01/06
5660
Юстас
Речь идет о гарантированном конечном времени (в худшем случае). Представьте, что на кубик для перемещения ему указывает вредная девочка Оля, которая хочет, чтобы Вася сортировал бесконечно долго. Сможет ли она добиться этой цели или же Вася рано или поздно все-таки отсортирует кубики, вопреки Олиному желанию?

 Профиль  
                  
 
 
Сообщение26.02.2009, 08:16 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Обозначим $h(i) =i-p(i)$ (от числа $i$ отняли занимаемую им позицию $p(i)$)
Если $h(i) = 0,$ то число $i$ стоит на подходящей позиции.

Приподнимем число $i$ с $h(i) > 0$ и перенесём его на свою позицию (сделав $h(i) = 0$). Если при этом переносе число $i$ пролетело над числами с неотрицательными $h,$ то величина $\sum_i|h(i)|$ не изменилась. А если пролетели хоть над одним отрицательным $h,$ сумма уменьшится. Однако (индукцией по длине участка с $h$ одного знака) нетрудно показать, что такие перелёты (не выходящие за участок одного знака и сохраняющие сумму $\sum_i|h(i)|$) не могут выполняться бесконечно. Сумма уменьшится. До нуля.

 Профиль  
                  
 
 
Сообщение26.02.2009, 08:54 
Заслуженный участник


09/02/06
4382
Москва
Если до перестановки i на свое место перестановка задавалась $p(j)$, то после операции перестановка задается через $p'(j)$, которое выражается так:
$p'(j)=p(j), j<min(i,p^{-1}(i)),j>max(i,p^{-1}(i)$
$p'(i)=i$,
$p'(j)=p(j+1),p^{-1}(i)\le j<i$ (p^{-1}(i)<i) $p'(j)=p(j-1),i<j\le p^{-1}(i)$.
Для функционала $$S(p)=\sum_i|i-p(i)|$$ верно $S(p')\le S(p)$ но строгого неравенства может не быть. Строгое неравенство вроде имеет место для другого положительного целочисленного функционала $$T(p)=\sum_i(p(i)-i)^2.$$

 Профиль  
                  
 
 
Сообщение26.02.2009, 11:00 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Руст писал(а):
Строгое неравенство вроде имеет место для другого положительного целочисленного функционала $$T(p)=\sum_i(p(i)-i)^2.$$

Такой другой функционал может даже возрастать.
$3, 100, 101$ дает $2^2+98^2+98^2$
Перенесём тройку на свое место и получим
$100, 101, 3$ то есть $99^2+99^2+0^2$

 Профиль  
                  
 
 
Сообщение26.02.2009, 13:53 


24/03/07
321
maxal писал(а):
Dandan писал(а):
Сумма \sum_i|i-p(i)| не увеличивается, а оставлять её такой же бесконечно мы не сможем, т.к. если эта сумма не меняется, то растёт количество инверсий.

Это неверно.
Например, в перестановке 42351 при перемещении 4 на свое место получается перестановка 23541 с тем же значением функции \sum_i|i-p(i)|, но меньшем числе инверсий.


ах да, нужно рассмотреть [инверсии - (количество чисел на своих местах)], кот. не уменьшается (при неизменности первого функционала). Если и этот не изменяется - то это только такие случаи, когда все сдвигаемые числа (кроме одного крайнего дальнего от дырки) стоят на своих местах (до сдвига). Типа вот этого (4)2351 -> 235(4)1. А дальше надо подумать ))

 Профиль  
                  
 
 
Сообщение26.02.2009, 16:48 
Модератор
Аватара пользователя


11/01/06
5660
TOTAL в сообщении #189656 писал(а):
Приподнимем число $i$ с $h(i) > 0$ и перенесём его на свою позицию (сделав $h(i) = 0$). Если при этом переносе число $i$ пролетело над числами с неотрицательными $h,$ то величина $\sum_i|h(i)|$ не изменилась. А если пролетели хоть над одним отрицательным $h,$ сумма уменьшится. Однако (индукцией по длине участка с $h$ одного знака) нетрудно показать, что такие перелёты (не выходящие за участок одного знака и сохраняющие сумму $\sum_i|h(i)|$) не могут выполняться бесконечно. Сумма уменьшится. До нуля.

Это примерно то же, о чем говорил Dandan выше. Вы не учитываете возможность перелета над нулевыми значениями $h(i)$ - попробуйте "нетрудно" провести упомянутую индукцию...

Добавлено спустя 20 минут 13 секунд:

Dandan в сообщении #189740 писал(а):
Если и этот не изменяется - то это только такие случаи, когда все сдвигаемые числа (кроме одного крайнего дальнего от дырки) стоят на своих местах (до сдвига).

Может быть больше одного, причем не обязательно с краю от дырки:
783456912 -> 834569712

 Профиль  
                  
 
 
Сообщение26.02.2009, 16:55 


24/03/07
321
maxal писал(а):
Может быть больше одного, причем не обязательно с краю от дырки:
783495612 -> 834956712

для этого примера первый фунционал уменьшается (для 7 изменение -6; для 8,9 изменение по +1; для 3,4 изменение по +1; а вот для 5,6 изменение по -1)

 Профиль  
                  
 
 
Сообщение26.02.2009, 16:59 
Модератор
Аватара пользователя


11/01/06
5660
Dandan
Дык это описка в примере. Вот вам другой:
783456912 -> 834569712

 Профиль  
                  
 
 
Сообщение26.02.2009, 17:36 


24/03/07
321
для него количество инверсий изменится на -2,
а количество чисел, стоящих на своих местах на -3 :wink:

Добавлено спустя 27 минут 28 секунд:

В этих особых случаях (когда первый и второй функционал не меняются) еще важно то, что вот то крайнее число (6ка в примере (4)23615 -> 236(4)15) относительно вставляемого числа (4ки) находится в правильном порядке (4 левее 6 до сдвига). Дальше получается так :
Смотрим на 1. Если мы ее трогаем (или она уже на своем месте), то по замечанию ИСН задача сводится к случаю n-1. Если мы её сдвигаем каким-то из вот этих наших особых случаев, то поскольку она не была на своем месте, значит она была крайней из сдвигаемых чисел. Получается двигаться единица может только вправо, значит с некоторого места мы её вообще не будем двигать. Дальше смотрим на 2ку. По идее должно получаться аналогично. Ну и т.д. :lol:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 58 ]  На страницу 1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group