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

[maxal]

Dandan
Вы близки к решению, но пока лишь топчитесь вокруг да около.

[TOTAL]

maxal писал(а):

TOTAL в сообщении #189656 писал(а):

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

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

Учитываю возможность, в моем решениии прямо указано про перелёт над неотрицательными $h(i),$ то есть и над нулевыми.

А индукция элементарна. Пусть на десяти первых местах значения $h(i)$ неотрицательны, а на одиннадцатом месте $h(i)<0.$ Я утверждаю, что можно сделать лишь конечное число ходов внутри этой первой десятки мест. Действительно, на десятое место можно сделать всего один ход, поэтому из предположения о бесконечности ходов внутри первой десятки следует бесконечность ходов внутри первой девятки, что невозможно (индукция!).

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

Всё, какие проблемы, чем это не доказательство?

[maxal]

TOTAL в сообщении #189979 писал(а):

А индукция элементарна. Пусть на десяти первых местах значения $h(i)$ неотрицательны, а на одиннадцатом месте $h(i)<0.$ Я утверждаю, что можно сделать лишь конечное число ходов внутри этой первой десятки мест. Действительно, на десятое место можно сделать всего один ход, поэтому из предположения о бесконечности ходов внутри первой десятки следует бесконечность ходов внутри первой девятки, что невозможно (индукция!).

Во-первых, почему вы предполагаете что в первой десятке (и почему именно 10-ке?) значения не отрицательны? Во-вторых, у вас наблюдается какая-то путаница - что значит "на десяти первых местах значения $h(i)$ неотрицательны" - если это $h(i)\geq 0$ для $i=1,2,\dots,10$, то из вашего же определения:

TOTAL в сообщении #189656 писал(а):

Обозначим $h(i) =i-p(i)$ (от числа $i$ отняли занимаемую им позицию $p(i)$)

просто следует, что $h(i)=0$ для всех $i=1,2,\dots,10$ (в частности, $h(1)$ не может быть больше нуля просто по определению).

Так что, если уж пишите доказательство, пишите так, чтобы подобных вопросов не возникало.

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

TOTAL в сообщении #189979 писал(а):

Я утверждаю, что можно сделать лишь конечное число ходов внутри этой первой десятки мест. Действительно, на десятое место можно сделать всего один ход, поэтому из предположения о бесконечности ходов внутри первой десятки следует бесконечность ходов внутри первой девятки, что невозможно (индукция!).

Кроме того, учитываете ли вы возможность, что эта 10-ка может быть расширена до 11-ки (12-ки и т.д.) ходом извне?
Подумайте еще над таким вопросом: какая оценка на максимальное число ходов в сотировке следует из вашего доказательства? Если это полиномиальная функция от $n$, то доказательство заведомо неверно - существуют сортировки длины экспоненциально зависящей от $n$.

[TOTAL]

maxal писал(а):

Во-первых, почему вы предполагаете что в первой десятке (и почему именно 10-ке?) значения не отрицательны? .

Замените десятку на двадцатку, что изменится?

maxal писал(а):

Во-вторых, у вас наблюдается какая-то путаница - что значит "на десяти первых местах значения $h(i)$ неотрицательны" - если это $h(i)\geq 0$ для $i=1,2,\dots,10$, то из вашего же определения:

TOTAL в сообщении #189656 писал(а):

Обозначим $h(i) =i-p(i)$ (от числа $i$ отняли занимаемую им позицию $p(i)$)

просто следует, что $h(i)=0$ для всех $i=1,2,\dots,10$ (в частности, $h(1)$ не может быть больше нуля просто по определению).

Из моего определения следует, что на первом месте стоит число не меньше единицы, на втором месте стоит число не меньше двойки и т.д. Как написано, от числа отнимите занимаемую им позицию и получите неотрицательные числа для первых десяти позиций. Все нормально.

maxal писал(а):

Кроме того, учитываете ли вы возможность, что эта 10-ка может быть расширена до 11-ки (12-ки и т.д.) ходом извне?
Подумайте еще над таким вопросом: какая оценка на максимальное число ходов в сотировке следует из вашего доказательства?

Меня нисколько не интересуют такие расширения за счет ходов извне. Я наблюдаю только за этой десяткой. Любой ход из этой десятки за пределы этой десятки приведет к перелёту через $h(i)<0,$ так как нельзя сделать ход на место с нулевым $h(i).$

[maxal]

TOTAL в сообщении #189983 писал(а):

Во-первых, почему вы предполагаете что в первой десятке (и почему именно 10-ке?) значения не отрицательны? .

Замените десятку на двадцатку, что изменится?

Не знаю. Но ясности использование 10-ки не превносит. Но основной вопрос был - почему в первой десятке неотрицательные значения, а не неположительные, например?

TOTAL в сообщении #189983 писал(а):

Обозначим $h(i) =i-p(i)$ (от числа $i$ отняли занимаемую им позицию $p(i)$)

Из моего определения следует, что на первом месте стоит число не меньше единицы, на втором месте стоит число не меньше двойки и т.д. Как написано, от числа отнимите занимаемую им позицию и получите неотрицательные числа для первых десяти позиций. Все нормально.

Позиция $p(1)$, занимаемая единицей, не может быть меньше 1, то есть $p(1)\geq 1$. Поэтому $h(1)=1-p(1)\leq 0$. Если вы говорите, что $h(1)$ неотрицательно, то $h(1)=0$.

TOTAL в сообщении #189983 писал(а):

Меня нисколько не интересуют такие расширения за счет ходов извне. Я наблюдаю только за этой десяткой.

За счет хода извне десятка может перестать быть 10-кой и стать 11-кой, например, тогда и возможных ходов в ней станей больше. Я понимаю ваше желание сфокусироваться на каком-то локальном участке, но для этого сначала надо доказать, что эти участки не могут влиять друг на друга.

[TOTAL]

maxal писал(а):

Не знаю. Но ясности использование 10-ки не превносит. Но основной вопрос был - почему в первой десятке неотрицательные значения, а не неположительные, например?

На первой позиции стоит число не меньше единицы, поэтому для первой позиции $h(i)$ неотрицательно. И так далее. Для наименьшей позиции с ненулевым $h(i)$ это $h(i)$ будет положительным. Очевидно.

maxal писал(а):

Позиция $p(1)$, занимаемая единицей, не может быть меньше 1, то есть $p(1)\geq 1$. Поэтому $h(1)=1-p(1)\leq 0$. Если вы говорите, что $h(1)$ неотрицательно, то $h(1)=0$.

При чем здесь позиция $p(1)$, занимаемая единицей? Речь идет о первых десяти (для примера) позициях.
На первой позиции стоит число $i \ge 1$ т.е $p(i)=1$

maxal писал(а):

Я понимаю ваше желание сфокусироваться на каком-то локальном участке, но для этого сначала надо доказать, что эти участки не могут влиять друг на друга.

Если делается ход внутри участка, то числа на других участках просто неподвижны.

Цепочка позиций начинается с участка с неотрицательными $h(i),$ за которым следует неположительный участок и т.д., заканчивается цепочка неположительным участком.

Любой ход внутри неотрицательного участка оставляет этот участок неотрицательным.
Аналогично неположительным.

[maxal]

TOTAL в сообщении #189985 писал(а):

На первой позиции стоит число не меньше единицы, поэтому для первой позиции $h(i)$ неотрицательно. И так далее. Для наименьшей позиции с ненулевым $h(i)$ это $h(i)$ будет положительным. Очевидно.

А так $i$ пробегает перевые элементы перестановки, а не числа $1..10$ - хоть что-то прояснилось.

TOTAL в сообщении #189985 писал(а):

Если делается ход внутри участка, то числа на других участках просто неподвижны.

Числа-то может и неподвижны, а вот границы участков - нет.
Например, в перестановке 2347156 начальный участок с неотрицательными значениями $h(i)$ - это 2347. Однако, ходом извне - ставя 5-ку на свое место этот участок расширяется до 23475.
Кроме того, даже если в этом начальном участке возможно лишь конечное число ходом, то может в каком-то другом - бесконечное (все-таки начальный участок - это в некотором роде особый случай)?

[TOTAL]

maxal писал(а):

Числа-то может и неподвижны, а вот границы участков - нет.
Например, в перестановке 2347156 начальный участок с неотрицательными значениями $h(i)$ - это 2347. Однако, ходом извне - ставя 5-ку на свое место этот участок расширяется до 23475.
Кроме того, даже если в этом начальном участке возможно лишь конечное число ходом, то может в каком-то другом - бесконечное (все-таки начальный участок - это в некотором роде особый случай)?

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

Для 2347156 имеется положительный участок 2347 и отрицательный участок 156. Ставя 5-ку на свое место мы не расширяем участок 2347 до 23475, а делаем ход внутри отрицательного участка 156 -> 516.

Начальный участок не является особым случаем. В любом неотрицательном участке можно сделать не более одного хода на место с самым большим номером. В любом неположительном участке можно сделать не более одного хода на место с самым маленьким номером. Так что внутри участка длиной $k$ можно сделать не более $2^k$ ходов.

[maxal]

TOTAL в сообщении #189990 писал(а):

Границы участков я устанавливаю и не меняю. В заданных с самого начала границах участок не может (при ходах внутри него) изменить свой знак.

А как же быть с "пограничными" участками с нулевой $h(i)$ - например, на какие участки разбивается 67845123 ?

TOTAL в сообщении #189990 писал(а):

В любом неотрицательном участке можно сделать не более одного хода на место с самым большим номером. В любом неположительном участке можно сделать не более одного хода на место с самым маленьким номером. Так что внутри участка длиной $k$ можно сделать не более $2^k$ ходов.

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

[TOTAL]

maxal писал(а):

А как же быть с "пограничными" участками с нулевой $h(i)$ - например, на какие участки разбивается 67845123 ?

678-45123
6784-5123
67845-123
Разбиваем любым из этих способов

Можно формировать также нейтральные участки, делая разбивку 678-45-123.
На нейтральном участке 45 вообще ничего не будет происходить. Доказательство не меняется.

Что касается оценки, то из моего решения для всей процедуры легко следует только грубая оценка
$(2^{p-1}-1)(2^{q-1}-1) \frac{S}{2},$ где
$p=[n/2], q=n-p$
$S$ - максимально возможное значение суммы $\sum_i|h(i)|$

(На участке одного знака длиной $k$ можно сделать не более $2^{k-1}-1$ ходов.)

[maxal]

TOTAL в сообщении #190010 писал(а):

Можно формировать также нейтральные участки, делая разбивку 678-45-123.
На нейтральном участке 45 вообще ничего не будет происходить. Доказательство не меняется.

Хотя ваша идея, похоже, рабочая, в доказательстве слишком много "степеней свободы", и есть опасность упустить какой-то ньюанс.
А у задачи тем временем есть короткое и четкое доказательство конечности сортировки без каких-либо вариаций.

[ewert]

давайте попробую. Я так понял, что Вася вполне автономен в своих действиях, и никакая Оля вмешаться в происходящее не в силах.

Шаг 1. Ищем неправильный кубик (всё равно в каком порядке -- пусть, для определённости, с начала). Ставим его в правильную позицию. Имеем минимум один правильный кубик; помечаем его как правильный.

Шаг 2. Ищем следующий неправильный кубик. Ставим его в правильную позицию. Если он не перескакивает при этом через предыдущий правильный, то все счастливы. В противном случае Вася знает, что предыдущий кубик стал неправильным, и переставляет его в правильную позицию. Имеем минимум два правильных кубика; помеченных как правильные.
. . . . . . . . . . . . . . . . . . . .

Шаг $k$. Ищем $k$-тый неправильный кубик. Ставим его в правильную позицию, засекая в памяти все уже помеченные, через которые мы при этом перелетаем. Если таковые нашлись, то возвращаем каждый из них в правильную позицию, начиная с ближайшего к $k$-тому. Имеем минимум $k$ правильных кубиков; помеченных как правильные.

Вот, вроде бы, и всё.

[maxal]

ewert в сообщении #190050 писал(а):

Я так понял, что Вася вполне автономен в своих действиях, и никакая Оля вмешаться в происходящее не в силах.

Как раз наоборот. Считайте, что Вася - это бездумный автомат, которым рулит Оля; или же Вася просто по договоренности следует Олиным вредным советам; или же сам хочет сортировать как можно дольше. Задача - доказать, что как бы Вася с Олей не пытались, сортировать бесконечно долго у них не получится.

[TOTAL]

ewert писал(а):

давайте попробую. Я так понял, что Вася вполне автономен в своих действиях, и никакая Оля вмешаться в происходящее не в силах.

Шаг 1. Ищем неправильный кубик (всё равно в каком порядке -- пусть, для определённости, с начала). Ставим его в правильную позицию. Имеем минимум один правильный кубик; помечаем его как правильный.

Шаг 2. Ищем следующий неправильный кубик. Ставим его в правильную позицию. Если он не перескакивает при этом через предыдущий правильный, то все счастливы. В противном случае Вася знает, что предыдущий кубик стал неправильным, и переставляет его в правильную позицию. Имеем минимум два правильных кубика; помеченных как правильные.
. . . . . . . . . . . . . . . . . . . .

Ха - ха - ха! При таком понимании задачи вот алгоритм:
Шаг i. Ставим $i$-ый кубик на $i$-ое место. И всё!

[ewert]

TOTAL писал(а):

Ха - ха - ха! При таком понимании задачи вот алгоритм:
Шаг i. Ставим $i$-ый кубик на $i$-ое место. И всё!

Безусловно, это алгоритм, несомненный алгоритм. Только вот для какой задачи?...

(вот ведь привереды) Ладно, тогда попробуем так.

По индукции: предположим (А), что утверждении (о конечности процедуры) верно для $(n-1)$ кубика. Докажем, чтогда оно верно и для $n$ кубиков.

Пусть начальная расстановка есть $(i_1,i_2,\ldots,i_{n-1},k)$, причём $k\neq n$ (иначе утверждение доказано). Среди первых $(n-1)$ кубиков есть кубик с номером $n$, номера же остальных кубиков лежат в диапазоне от $1$ до $(n-1)$, причём номер $k$ пропущен.
За конечное количество шагов произойдёт одно из двух.

(В) Будет сделана попытка переставить кубик с номером $k$, стоящий на $n$-ной позиции.

(С) Будет сделана попытка переставить кубик с номером $n$, находящийся на начальном участке. Это верно по следующим причинам. Временно пометим кубик с номером $n$ из начального участка номером $k$. По предположению (А), рано или поздно начальный участок окажетса выстроен по ранжиру (так, что кубик с фактическим номером $n$ jокажется в $k$-той позиции) -- если только перед этим не будет сделана попытка переставить кубик с номером $n$ или с номером $k$. Но если последнего не произойдёт, то мы вынуждены будем переставить один из этих двух кубиков на следующем шаге.

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