сортировка случайными вставками

[juna]

maxal в сообщении #189652 писал(а):

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

Ну а если зловредная Оля всегда будет указывать на кубик с предыдущего шага?
Т.е. надо поправиться, что нельзя выбирать кубик с предыдущего шага.
Ну а если Оля выбирает первый или последний кубик, то задача сократится на один кубик, поэтому пусть не выбирает. Но если последний идет раньше первого, то труды Васи тоже бесполезны. Так что нужно тоже поправиться - можно выбирать только так, чтобы на следующем шаге менялась относительно предыдущего. Но тогда рано или поздно придем к расположению, когда последний будет первым, первый последним, а все остальные внутри. Но тогда Оле нельзя трогать второй и предпоследний. А дальше повторяем рассуждения и приходим к заключению, что Оле ничего нельзя выбирать.

[maxal]

juna в сообщении #190180 писал(а):

Ну а если зловредная Оля всегда будет указывать на кубик с предыдущего шага?

По определению нельзя выбирать кубики стоящие на своих местах. Именно таким кубиком будет перемещенный на предыдущем ходе.
Но этот кубик может впоследствии быть сдвинут со своего места перемещениями других кубиков, и снова стать доступным для перемещения на свое место. То есть принципиально существует возможность зациклиться - и эта задача как раз о том, что такой возможности на самом деле нет То есть, как не перемещай кубики согласно правилам, рано или поздно они все отсортируются.

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

Более того (вторая часть задачи), предлагаю доказать, что перестановка порядка $n$ отсортируется максимум за $2^{n-1}-1$ вставок, причем этот максимум достижим на некоторой перестановке.

[Руст]

Похоже последнее и есть подсказка. Ставим последовательности $p(i)$ число в двоичном разряде у которого на i слева (отсчёт от больших) разряде число 0, если $p(i)\le i$ и 1 иначе. Это и есть искомый функционал.

[maxal]

Руст
Что-то функционал какой-то несимметричный относительно $p(i)<i$ и $p(i)>i$, в то время как на перестановках $(p(1),\dots,p(n))$ и $(n+1-p(n),\dots,n+1-p(1))$ он по идее должен давать одно и то же значение.

[Руст]

Можно взять и симметричный, т.е. суммы с двойственной, ни один так другой уменьшится.

[juna]

maxal в сообщении #190182 писал(а):

принципиально существует возможность зациклиться - и эта задача как раз о том, что такой возможности на самом деле нет

Тогда такая идея.
Пусть $a_1,a_2,...,a_n$ - расположение на $k$-м шаге, $b_1,b_2,...b_n$ - расположение на $k+1$ шаге. Тогда $\forall k:\sum\limits_{i=1}^{n}(a_i-b_i)=0$. Поэтому для каждого расположения $a_1,a_2,...,a_n$ существует единственное $b_1,b_2,...b_n$ (ведь в расположении на $k+1$-м шаге обязательно будут отличия от $k$ шага ) и циклов не предвидится.

[maxal]

Руст в сообщении #190207 писал(а):

Можно взять и симметричный, т.е. суммы с двойственной, ни один так другой уменьшится.

А получится ли при этом доказательство достижимой верхней оценки $2^{n-1}-1$ ?

Добавлено спустя 2 минуты 16 секунд:

juna в сообщении #190241 писал(а):

Поэтому для каждого расположения $a_1,a_2,...,a_n$ существует единственное $b_1,b_2,...b_n$

Очевидно, это неверно.
Например, из перестановки $a=(2,1,4,3)$ можно сделать четыре различных хода и получить таким образом две различных перестановки $b$.

[Руст]

Пусть $p(j)$ число на j-ом месте слева, j=1,2,...,n.
Определим функционал

$$S_1=\sum_{j=1}^n2^{n-j}(p(j)>j)$$

, где число $(p(j)>j)=1$ если выполняется условие $p(j)>j$, иначе 0. Если выбранное число $i=p(j)>j$, то после перестановки это число на свое место значение функционала уменьшится. Если $i=p(j)<j$, то он не уменьшится, если $p(k)\le k,$ для всех $k=i,...,j-1$. Это компенсируется введением симметричного функционала

$$S=\sum_{j=1}^n2^{n-j}(p(j)>j) +\sum_{j=1}^n 2^{j-1}(p(j)<j).$$

При этом функционал уменьшится как минимум на $2^{min(i-1,j-1)}.$
Конечно можно оценить количество малых шагов уменьшения и получить оценку mahal а. Однако, мне интуиция подсказывает, что и эта оценка слишком завышенная. Скорее всего для максимального количества шагов верна оценка $O(n^2)$, возможно $\frac{n(n-1)}{2}$.

[TOTAL]

ewert писал(а):

TOTAL писал(а):

Ха - ха - ха!

Если же переставится последний кубик (предположение (В)), то она продолжится, но не слишком долго. Просто потому, что кубик, вытесненный или перемещённый с последней позиции, обратно вернуться уже не сможет.

Ха - ха - ха! Кубик, перемещённый с последней позиции, обратно вернуться сможет.
Вот окончание цепочки
..., 2, 3, n-2 -> ..., n-2, 2, 3 -> ..., n-2, 2 -> ..., n-2 Бинго!

---------------------------------------------------------------------------------------------------------------------------------

Вот доказательство без функционалов.

Так как Васе уже внушили, что на отрезке короче чем $N$ он зациклиться не сможет, то он озабочен судьбой цифры $1.$ Если сходить единицей, то сразу капут. Долго держать единицу в одной и той же позиции он тоже не сможет, так как слева и справа от единицы будут два коротких интервала, на которых он долго не заиграется. Следовательно, единицу необходимо бесконечное число раз сдвигать путем переноса через неё других чисел. Пусть $P$ - наименьшее из чисел, каждое из которых (предположительно) сколь угодно много раз переносится через единицу. Дождемся момента, когда числа меньшие чем $P$ свои конечные количества прыжков через единицу уже совершили, и перепрыгнем числом $P$ через единицу, сдвинув её на позицию меньше $P.$ Всё, вот и число $P$ отпрыгалось! Конец доказательства.

[Dandan]

это неправильно

[ИСН]

TOTAL, подходы на локальных инвариантах бесперспективны, потому что локальности у нас нет. Конкретно, в описанной ситуации ничто не мешает единице и числу $P$ потом отдрейфовать вправо, так что это число сможет опять "своим ходом" прыгнуть через единицу, только в другую сторону.
Так что нет; только глобальные функционалы.
Касательно же оценок, мне представлялось что-то типа Ханойской башни, выстраиваемой с середины отрезка... но после слов Руста усомнился. After all, в этой модели каждый новый юнит её всего лишь портит единичным сдвигом, а не ставит с ног на голову.

[Руст]

На самом деле задача решается проще и максимальное количество ходов оценивается величиной $[\frac{n^2+1}{2}]$. Точно не проверил, кажется при некотором начальном расположении Оля всегда может добится того, чтобы количество ходов было равно именно этому числу. Пока полученного решения не даю, оставлю другим участникам.

[maxal]

Руст в сообщении #190565 писал(а):

На самом деле задача решается проще и максимальное количество ходов оценивается величиной $[\frac{n^2+1}{2}]$.

Это неверно. Максимальное достижимое число ходов равно $2^{n-1}-1$.

[Руст]

Придётся дать рассуждение, которое приводит к оценке $[\frac{n^2+1}{2}]$.
Расмотрим число 1 или n. Их на свои места придётся ставит не более одного раза. Рассмотрим 2. Если мы поставим её на место, то её может потребоваться ставит на место ещё 2 раза, один раз после установления 1 и один раз после установления первого числа. Т.е. передвижений числа 2 не более 3 раз. Аналогично для n-1.
При установлении числа i<=n/2 после одного установления может потребоваться ещё раз устанавливать не более i-1 раз (после каждой установки чисел меньших n) и i-1 раз после переставления чисел больших i, но занимающих позиции не более i-1. Всего не более 2i-1.
Суммируя эти числа получаем указанную верхнюю оценку.
Где пробелы в рассуждении?

[maxal]

Руст в сообщении #190568 писал(а):

Рассмотрим 2. Если мы поставим её на место, то её может потребоваться ставит на место ещё 2 раза, один раз после установления 1 и один раз после установления первого числа. Т.е. передвижений числа 2 не более 3 раз.

Здесь ошибка.
Вот пример с более чем 3-мя перемещениями 2-ки:
456217x
425617x
256417x
526417x
264157x
624157x
241576x
421576x
...