Количество размещений "кактуса" по n (комбинаторная задача)

[Mihaylo]

Итак, чуть продвинулся вперед:
1) Доказал, что максимум произведения $PC_1\cdot PC_2$ достигается при $PC_1=PC_2=\frac{PC_0}{2}$. Подтверждаются Ваши слова: максимум 1 бит можно ожидать от сравнения двух чисел.
2) Доказал, что если взять два одинаковых дерева и сравнить их корни, то из них получится дерево, имеющее вдвое меньшее число перестановок $PC$. Примечательно, что это значение не обладает свойством случайности.
3) Изначально имеем $n$ одновершинных деревьев. Это базис индукции, шаг индукции был обозначен в п. 2. Для простоты принял, что число $n$ - является степенью двойки (32, 64, 128 и т.д.). По индукции определил, что за первые $(n-1)$ итераций оптимальный алгоритм должен построить хитрое дерево из $n$ вершин.
4) Это первый этап алгоритма, далее идет какой-то другой алгоритм, так как дерево осталось одно. Придется доказывать другие утверждения.
5) Количество итераций жадного алгоритма составляет не менее $n-1$ и такой алгоритм на некоторых особенных массивах будет проигрывать более удачливым алгоритмам типа быстрой сортировки (QUICK-SORT) и т.д. Первая часть алгоритма получается устойчивая, то есть количество итераций и время работы не зависит от значений чисел массива, которые нужно сортировать.
6) Очевидно алгоритм соответствует принципу "разделяй и властвуй". Алгоритм в каком-то смысле очень похож на алгоритм пирамидальной сортировки (HEAP-SORT), который также состоит из двух частей - первые $\left\lfloor\frac{n}{2}\right\rfloor$ итераций создается куча (heap), а во второй части алгоритма эта куча сортируется.
7) Пока не доказано, единственный ли такой алгоритм.

[Mihaylo]

Mihaylo писал(а):

2) Доказал, что если взять два одинаковых дерева и сравнить их корни, то из них получится дерево, имеющее вдвое меньшее число перестановок $PC$. Примечательно, что это значение не обладает свойством случайности.

Доказал более общее утверждение:
Если сравнить корни двух произвольных деревьев с количеством вершин $n_1$ и $n_2$, то число перестановок $PC$ изменится в $\frac{n_1^2+n_2^2}{(n_1+n_2)^2}$ раз.

Отсюда следует, что, если сравнить произвольные деревья с одинаковым количеством вершин $n_1=n_2$, то число перестановок уменьшится вдвое. То, что надо.

После работы первой части алгоритма сортировки определяется максимальное (или минимальное) число массива. Это число уже отсортировано и его можно убрать из рассмотрения. В результате дерево из $n$ вершин рассыпается на $\log_2(n)$ деревьев с разным числом вершин: 1, 2, 4, 8, ..., $\frac{n}{2}$. В связи с этим прежний алгоритм сравнения корней не будет давать оптимальный результат. Не совсем пока ясно, существуют ли иные варианты сравнения, которые дают результат более близкий к 1 биту...

[Mihaylo]

Mihaylo писал(а):

Если сравнить корни двух произвольных деревьев с количеством вершин $n_1$ и $n_2$, то число перестановок $PC$ изменится в $\frac{n_1^2+n_2^2}{(n_1+n_2)^2}$ раз.

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

Это утверждение очень сильное, но пока недостаточное, чтобы успокоиться. Хотя, наверное, пора уже успокоиться и искать-таки решение, а не доказательства о несуществовании.

[iancaple]

Mihaylo в сообщении #1049997 писал(а):

Если сравнить корень любого дерева, который получился в результате работы первой части жадного алгоритма, с произвольной вершиной другого дерева из этой группы, то число перестановок никогда не уменьшится ровно в два раза. То есть такие сравнения не дадут идеальный результат.

1-ю часть я понимаю иначе: в результате $\sim\log_2n$ сравнений все элементы соберутся в одном дереве, вид которого мы знаем. Дальше можно уступить в "жадности", но добавить "системности", на каждом шаге 1)сохраняя регулярное (без срастаний) дерево 2)сравнивая элементы так. что вероятности исходов сравнения отличаются не более чем вдвое (а число перестановок в дереве уменьшится, как минимум в полтора раза)
И так можно, пока не получится линейное дерево, что значит: гарантированное упорядочение за не более чем $\log_{3/2}(n!)$ сравнений. Менее чем вдвое хуже по числу сравнений, чем теоретический минимум $\log_2(n!)$
Но в силу того, что мы описываем алгоритмы в совсем других терминах, чем описаны известные - затрудняюсь сказать, близок ли он к известным. Ну и по удобству реализации неясно, слежение за деревом или за матрицей смежности - это тоже время.

[Mihaylo]

iancaple писал(а):

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

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

[Mihaylo]

Mihaylo писал(а):

конечный результат сортировки не сильно важен

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

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

[iancaple]

На этом примере никакой разницы между 1)минимизацией энтропии (максимизацией информации), 2)минимизации матожидания числа оставшихся вариантов и 3) обычным принципом минимакса (минимизировать время работы для наихудшего стечения обстоятельств) наблюдать не будем, т.к. мы имеем дело со сравнениями, у которых 2 исхода.
Но мне было интересно взглянуть на такую известную тему и с этих позиций

[Mihaylo]

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

Вообще для любого алгоритма можно вычислить изменение энтропии во времени, для рекурсивных алгоритмов это особенно интересно, у них получается зависимость "энтропия-итерация" вида $H(i)$. Вот, например, для алгоритма Евклида нахождения НОД двух чисел $a$ и $b$ справедлива зависимость $H(i)=\log[\max(r_i,1)]$, где $r_i$ - это остаток от деления, полученный в $i$-й итерации; при этом считать $r_0=\infty$, $r_1=\min(a,b)$, итерация $i=0$ соответствует моменту времени до начала выполнения алгоритма.

Самое интересное, что если функция $H(i)$ зависит только от $i$, то тогда алгоритм является устойчивым - время его работы не зависит от входных данных. Иначе алгоритм неустойчивый. Если при определенных входных данных энтропия $H(i)$ при некотором $i$ принимает нулевое значение, значит алгоритм способен выполнить задачу. Это, правда, не означает, что алгоритм останавливается... Короче, этот факт лишь подтверждает, что энтропия и сложность - это разные понятия.

Некоторое время не мог придумать какую-нибудь полезную отдачу от вычисления $H(i)$... Не знаю, может в этом кроется какой-нибудь гораздо более мощный инструмент, чем кажется?

[arseniiv]

Mihaylo в сообщении #1050833 писал(а):

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

Для «почти сортировки» разве поле алгоритмов не распахано, если уже не поперёк, то хотя бы вдоль? Кажется, краем уха что-то на эту тему слышал.

Сортировки «до конца» с минимумом сравнений хотя бы у Кнута в «Искусстве…» (том 3) рассматриваются, хотя особо не вчитывался, чтобы сравнить.

[Mihaylo]

Что касается алгоритма сортировки: первая часть алгоритма настолько жадная, что трудно придумать разумно устроенную вторую часть алгоритма - граф сортировки хоть и может сохранять свойство "дерево", но структура леса становится столь нерегулярной - сильно зависит от входных данных. При любом дальнейшем алгоритме придется использовать дополнительную память для хранения истории сравнений (=структура графа сравнения).
Предлагаю придерживаться алгоритма со следующими свойствами:
1. Сравнивать между собой только корни деревьев - это позволит поддерживать свойство структуры данных "лес".
2. Структуру графа сравнения хранить в массиве $T[i]$, где $i$ - это номер элемента в сортируемом массиве $A[i]$. $T[i]$ - это число вершин, входящих в поддерево $i$-го элемента. Чтобы перейти к следующему дереву или поддереву, достаточно увеличить $i$ на величину $T[i]$. Если происходит выход за пределы, то значит деревьев и поддеревьев больше нет.
3. Сравнивать корни двух крайних левых деревьев леса. Пусть $i$ - это номер корня самого левого дерева.
3.1. Если корень самого левого дерева больше следующего ($A[i]>A[i+T(i)]$), то достаточно изменить $T[i]$ этого корня: $T[i]:=T[i]+T[i+T[i]]$ - это операция сращивания двух левых деревьев.
3.2. Иначе придется обменивать самое левое дерево с корнем дерева правее. Довольно затратная операция, но все же. После обмена также изменить $T[i]$ по формуле выше (операция сращивания).

Возможно данный алгоритм очень даже оптимальный по нашему критерию?

-- 06.09.2015, 22:02 --

arseniiv писал(а):

Для «почти сортировки» разве поле алгоритмов не распахано, если уже не поперёк, то хотя бы вдоль? Кажется, краем уха что-то на эту тему слышал.

Может речь шла о сортировке частично сортированных массивов? Про такие алгоритмы я слышал, например, алгоритм TimSort применяется в ОС Android.

arseniiv писал(а):

Сортировки «до конца» с минимумом сравнений хотя бы у Кнута в «Искусстве…» (том 3) рассматриваются, хотя особо не вчитывался, чтобы сравнить.

Спасибо, еще раз загляну в этот труд.

[Mihaylo]

Mihaylo в сообщении #1050998 писал(а):

при этом считать $r_0=\infty$, $r_1=\min(a,b)$,

Извините, поторопился. Конечно же достаточно считать $r_0=\min(a,b)$, никаких бесконечностей.

[arseniiv]

Mihaylo в сообщении #1051036 писал(а):

Может речь шла о сортировке частично сортированных массивов?

Да вроде бы и о частичной сортировке любых.

[Mihaylo]

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

[arseniiv]

У меня, увы, нет.

[Mihaylo]

Mihaylo писал(а):

Предлагаю придерживаться алгоритма со следующими свойствами:
1. Сравнивать между собой только корни деревьев - это позволит поддерживать свойство структуры данных "лес".
2. Структуру графа сравнения хранить в массиве $T[i]$, где $i$ - это номер элемента в сортируемом массиве $A[i]$. $T[i]$ - это число вершин, входящих в поддерево $i$-го элемента. Чтобы перейти к следующему дереву или поддереву, достаточно увеличить $i$ на величину $T[i]$. Если происходит выход за пределы, то значит деревьев и поддеревьев больше нет.
3. Сравнивать корни двух крайних левых деревьев леса. Пусть $i$ - это номер корня самого левого дерева.
3.1. Если корень самого левого дерева больше следующего ($A[i]>A[i+T(i)]$), то достаточно изменить $T[i]$ этого корня: $T[i]:=T[i]+T[i+T[i]]$ - это операция сращивания двух левых деревьев.
3.2. Иначе придется обменивать самое левое дерево с корнем дерева правее. Довольно затратная операция, но все же. После обмена также изменить $T[i]$ по формуле выше (операция сращивания).

Поразмышлял и придумал следующую вторую часть алгоритма:
1. Сравнить корни двух крайних деревьев.
2. Если правый корень больше левого корня, то произвести обмен (swap) двух деревьев.
3. Срастить левое дерево с правым (при этом корень левого дерева должен взять в потомки корень правого дерева).
4. Если есть еще деревья, то перейти к п.1.
5. Отбросить корень единственного дерева из рассмотрения - мегадерево снова распадется на несколько деревьев.
6. Если есть еще вершины, то перейти к п. 1.
7. Конец сортировки.

В таком алгоритме имеются следующий инварианты:
1. Каждый раз сохраняется лес деревьев (об этом уже говорил).
2. Каждый раз деревья располагаются по неубыванию $T[i]$ корней, поэтому сравнение двух соседних деревьев получается достаточно эффективным по уменьшению энтропии.

Попробую написать алгоритм в Mathcad и потестировать его.