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

[Mihaylo]

Реализовал алгоритм в Mathcad, все работает. Практический результат следующий: сортируем массив 128 случайных чисел, получается алгоритм делает примерно 728...745 сравнений при идеальном минимуме $\log_2(128!)=716,2$.
Алгоритм состоит из двух частей: первая часть сортирует жадно и идеально ($(n-1)$ итерация), затем вторая часть - "подчищает" за первой. Обе части алгоритма по принципу работы получились очень похожи и при некоторых сравнениях вызывают довольно затратную функцию SWAP_BLOCK, которая обменивает местами блоки элементов массивов (обменивает левое и правое деревья местами).

Очень мощно алгоритм сортирует частично сортированные массивы! На сортировку монотонных массивов типа $X_i=i$, $X_i=-i$ алгоритм тратит одинаково 448 операций сравнения. Массив $X_i=64^2-(i-64)^2$, который сначала возрастает, затем убывает - 510 итераций. Массив $X_i=30\cdot\sin(2\pi\frac{5i}{n})$ с десятью участками монотонности сортируется за 645 итераций.

Я задался вопросом, а существуют ли те самые идеальные алгоритмы, которые завершают полную сортировку случайных и неслучайных чисел, всегда укладываясь в $\log_2(n!)$ итераций сравнения?

[iancaple]

1.Почему Вы сортировку реализовали как физический обмен, более естественна была бы индексация. Может пришлете (15я версия?), попробую быстро изменить.
2.Информационный минимум $\log_2N$, где $N$ число вариантов конечного результата, может и не достигаться, это связано с ограниченностью возможностей языка, на котором "задают вопросы". Здесь Вы можете спросить только про исход конкретного сравнения, а не любой вопрос с ответом да/нет. В задачах на взвешивания такой пример специально придуман, см. задачу ММ126.topic16349-75.html

[Mihaylo]

1. У меня Mathcad Prime 3.1. Объясните про индексацию. Предлагаете просто менять указатели (pointers) на элементы массива? Или что-то другое?
2. Спасибо, следует рассмотреть решение задачи...

$A$ - сортируемый массив, $A[0]$ - первый элемент массива
$T$ - массив структуры графа сортировки

Псевдокод алгоритма:

ENTHROPY_SORT(A)
    for i=0 to n-1
        T[i]:=1   //инициализация структуры графа сортировки
    for i=1 to log2(n)                                          // ЧАСТЬ 1
        for j=0 to n/2^i-1
            if A[j*2^i] > A[j*2^i+2^(i-1)]     // сравнение корней деревьев
                SWAP_TREE(j*2^i, 2^(i-1), 2^(i-1)) // перестановка деревьев
            T[j*2^i]:=T[j*2^i]+T[j*2^i+2^(i-1)]   // сращивание деревьев
    for i=1 to n-1                                                // ЧАСТЬ 2. Одна вершина уже найдена, остались n-1
        while (i+T[i]<n)                                       // пока деревья не закончились...
            if A[i] > A[i+T[i]]                                 // сравнение корней деревьев
                SWAP_TREE(i, T[i], T[i + T[i]])         // перестановка деревьев
            T[i]:=T[i]+T[i + T[i]]                           // сращивание деревьев

SWAP_TREE - функция перестановки подмассивов.
Первый подмассив начинается с индекса start и имеет длину n1.
Второй подмассив начинается с индекса (start+n1) и имеет длину n2.

SWAP_TREE(start,n1,n2)
    for j=0 to n2-1
        swap[start+j]:=A[start+n1+j]
        swapt[start+j]:=T[start+n1+j]
    for j=0 to n1-1
        swap[start+n2+j]:=A[start+j]
        swapt[start+n2+j]:=T[start+j]
    A:=swap
    T:=swapt

Я пока не заботился о быстродействии и экономии памяти в функции SWAP_TREE. Очевидно, можно уменьшить размеры массива swap и swapt до величины $\min(n_1,n_2)$, но тогда алгоритм станет чуть менее понятный.

[iancaple]

Да, все перестановки делать с указателями (числа $1,...n$), а операция сравнения косвенная:

if A[j*2^i] > A[j*2^i+2^(i-1)]     // сравнение корней деревьев
заменится на:
if A[P[j*2^i]] > A[P[j*2^i+2^(i-1)]]     // сравнение корней деревьев

Это дает экономию при сортировке нечисловых данных, например фрагментов из сети.
Не вижу, как Вы добиваетесь, чтобы ветви, выходящие из одной вершины, располагались по возрастанию их веса. Т.к. после того, как найден наименьший элемент (например, наименьший из семи), из него будут, возможно, выходить ветви весами 1,2,3, и тогда надо, по согласованному нами принципу оптимизации, сначала сравнивать ветви с весами 1 и 2, объединять их в ветвь с весом 3 и сравнивать с другой ветвью весом 3 . И такая возможность будет на каждом этапе алгоритма: Последовательность весов ветвей, выходящих из одной вершины, упорядоченная по возрастанию, не будет иметь отношений соседних чисел более, чем 2, а отношение элемента к сумме предшествующих не менее $\frac 12$. Это и позволило мне ранее утверждать, что вероятности исходов каждого сравнения, вплоть до последнего, отличаются не более чем вдвое.
А тут я не вижу, как Вы отслеживаете веса ветвей (числа вершин поддеревьев).
Ну дальше уже специфика началась, лучше Вам говорить с теми, кто может эту прогу гонять у себя.

[Mihaylo]

iancaple писал(а):

А тут я не вижу, как Вы отслеживаете веса ветвей (числа вершин поддеревьев).

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

iancaple писал(а):

Ну дальше уже специфика началась, лучше Вам говорить с теми, кто может эту прогу гонять у себя.

Я уже закинул удочку.

[Mihaylo]

Сравнение алгоритма ENTHROPY-SORT с другими популярными алгоритмами, критерий сравнения - количество сравнений чисел:
1) Быстрая сортировка (QUICKSORT). На случайных массивах QUICKSORT также придерживается минимума сравнений $\log_2 n!$, но несколько нестабильно, хуже. Известно, что QUICKSORT работает отвратительно на частично сортированных массивах, поэтому можно сказать, что ENTHROPY_SORT по количеству сравнений однозначно лучше QUICKSORT.
2) Пирамидальная сортировка (HEAPSORT). Совершенно ужасный алгоритм по данному критерию. При $n=128$ случайных числах алгоритм производит примерно 1500-1800 сравнений для любых массивов. ENTHROPY-SORT делает 440-750 сравнений.

[arseniiv]

(Оффтоп)

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

ENTHROPY-SORT

Если вы не хотите, чтобы от названия хихикали, смените в нём первое слово лучше на entropy.

[Mihaylo]

Арсений, спасибо, не заглядывал в словарь :)

[Mihaylo]

Наконец-то добрался до алгоритма сортировки слиянием (MERGESORT):
3) По критерию количества сравнений достаточно хороший. Можно даже вычислить теоретически, число сравнений равно $n\log_2 n$ независимо от характера данных, то есть на частично сортированных массивах алгоритм неоптимален.
Отклонение от идеальности $n\log_2 n-\log_2 n!\approx 1,44n$ линейно возрастает с ростом размера данных.

Еще обнаружил следующее:
Д.Э.Кнут "Искусство программирования", том 3. Раздел 5.3.1 "Сортировка с минимальным числом сравнений".

Цитата:

Из всех известных нами методов сортировки три метода требуют меньше всего сравнений: бинарные вставки (см. раздел 5.2.1), выбор из дерева (см. раздел 5.2.3) и простое двухпутевое слияние, описанное в алгоритме 5.2.4L).

Число сравнений в наихудшем случае для метода бинарных вставок
$B(n)=\sum\limits_{k=1}^{n}\left\lceil \log_2 k\right\rceil=n\left\lceil\log_2 n\right\rceil-2^{\left\lceil\log_2 n \right\rceil}+1$
Сортировка слиянием списков
$L(n)=\sum\limits_{k=1}^{t}[(e_k+k-1)2^{e_k}]-2^{e_t}+1$, где $e_k$ - это степени двойки в двоичном представлении числа $n$
$n=2^{e_1}+2^{e_2}+...+2^{e_t}$, где $e_1 > e_2 > ... > e_t$, $t\geqslant 1$

Далее Кнут анализирует еще один алгоритм - сортировка методом вставок и слияния, который оказывается очень и очень хорошим
$F(n)=\sum\limits_{k=1}^{n}\left\lceil \log_2 \frac{3}{4}k\right\rceil$

Вывод: по наихудшему случаю алгоритм ENTROPYSORT несколько хуже, чем сортировка методом вставок и слияния, но не хуже бинарной вставки. Буду смотреть, как ведут себя алгоритмы при частично упорядоченных числах...

[Mihaylo]

Рассматриваемый нами алгоритм ENTROPY-SORT (без сортировки деревьев по возрастанию весов) абсолютно соответствует алгоритму "выбор из дерева" (раздел 5.2.3) по структуре дерева сравнений. Отличие в том, что в "выборе из дерева" выбывающие корни записываются в отдельный массив, а в рабочем массиве они заменяются на $-\infty$ и помещаются в листья дерева, а структура дерева остается всегда такая, какая получена после первой части алгоритма ENTROPY-SORT.
При дальнейшей оптимизации алгоритма "выбор из дерева" Кнут приходит к идее убрать как-нибудь $-\infty$ из рабочего массива и таким образом получается пирамидальная сортировка (HEAPSORT).

[iancaple]

Вот попытаться бы сделать, чтобы при неожиданном прерывании сортировки у Вас результат был максимально вероятный из возможных. Можно хранить и обновлять 2 числовые характеристики каждого элемента, назову их "число побед" и "число поражений". Число побед данного элемента - это число элементов, про которые мы точно знаем, что они "хуже" данного (в этом алгоритме-больше), с каждым благоприятным исходом сравнения оно нарастает не на единицу, а на вес всего поддерева, корнем которого является "проигравший" элемент. Также оно может нарастать, и когда элемент не участвует в сравнении.
А можно эти характеристики и и не обновлять, а после команды на прерывание вытащить из текущего дерева, смотря как оно упаковано (это место в маткаде я не понял). И как-то из них скомпоновать рейтинг элемента.

[Mihaylo]

iancaple писал(а):

Вот попытаться бы сделать, чтобы при неожиданном прерывании сортировки у Вас результат был максимально вероятный из возможных. Можно хранить и обновлять 2 числовые характеристики каждого элемента, назову их "число побед" и "число поражений". Число побед данного элемента - это число элементов, про которые мы точно знаем, что они "хуже" данного (в этом алгоритме-больше), с каждым благоприятным исходом сравнения оно нарастает не на единицу, а на вес всего поддерева, корнем которого является "проигравший" элемент. Также оно может нарастать, и когда элемент не участвует в сравнении.
А можно эти характеристики и и не обновлять, а после команды на прерывание вытащить из текущего дерева, смотря как оно упаковано (это место в маткаде я не понял). И как-то из них скомпоновать рейтинг элемента.

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

--------
Откатимся несколько назад. Можно рассматривать три вида оптимальных алгоритма:
1. Жадный на ожидаемую негэнтропию
2. Оптимальный по количеству сравнений в наихудшем случае
3. Оптимальный по количеству сравнений в среднем
Риторические вопросы: одинаковы ли эти алгоритмы? чем они отличаются?

Займемся жадным алгоритмом

Mihaylo писал(а):

1) Доказал, что максимум произведения $PC_1\cdot PC_2$ достигается при $PC_1=PC_2=\frac{PC_0}{2}$. Подтверждаются Ваши слова: максимум 1 бит можно ожидать от сравнения двух чисел.

Напомню, $PC_1$ - количество перестановок в случае, когда результат сравнения $a_i<a_j$, а $PC_2$ - когда результат сравнения противоположный $a_i>a_j$.
Поставим на повестку дня вопрос существования идеального жадного алгоритма, который на каждом шаге добивается 1 бита ожидаемой информации. Рассмотрим сортировку с конца. В конце сортировке граф сравнений представляет собой простую цепь из $n$ элементов. Для простоты примем, что $n$ является степенью двойки (32, 64, 128, 256 и т.д.). Допустим в конце сортировки реализовался первый исход сравнения, т.е. $PC_1=1$, соответственно вариант $PC_2$ не реализовался. Если доказать, что не существуют варианты сравнения, при котором $PC_1=PC_2$, то это будет означать несуществование идеального жадного алгоритма.
Для этого в простой цепи уберем ребро между $i$-ой и $(i+1)$-ой вершиной и посчитаем $PC_2$ для того случая, если бы результат сравнения был противоположный. Получено выражение $PC_2=\sum\limits_{j=1}^{i}C^{j}_{n-i-1+j}$, которое принимает минимальное значение $C^{1}_{n-1}=n-1$ при $i=1$ или $i=n-1$. Таким образом идеальный жадный алгоритм существует только при самом простейшем случае сортировки $n=2$. Предельная достижимая негэнтропия на последнем шаге сортировки равна $\log_2\frac{n^2}{n^2-2n+2}$.

[Mihaylo]

Если я правильно понимаю, то задача может быть сведена к теории чисел следующим образом: необходимо взять факториал $n!$ и разложить его на простые множители. Например, $8! = 40320 = 2^7\cdot 3^2 \cdot 5 \cdot 7$. Отсюда следует, что жадный алгоритм сможет 7 итераций ($n-1=7$) получить максимальное количество итераций (этот алгоритм известен), а дальше уже "приходится учитывать угловатости несимметричных структур и дискомфорт простых чисел". Нужно найти связь между структурами и разложением чисел. Так?

[iancaple]

Давайте на примере. Для 5 элементов жадным алгоритмом сделали 3 сравнения $a_1<a_2,a_3<a_4,a_1<a_3$ Число перестановок $\frac{5!}8=15$, вообще никто не гарантировал, что очередным сравнением их можно разбить на 7 и 8. Возможно 4 сравнения с участием нетронутого элемента:
$P(a_5<a_1)=\frac 3{15}$
$P(a_5<a_3)=\frac 7{15}$(тут повезло)
$P(a_5<a_2)=\frac 9{15}$
$P(a_5<a_4=\frac {11}{15}$
И тут 2 соображения: 1)а почему бы их, если не удается закончить сравнения, не расположить в порядке возрастания (вероятностей) $(a_1,a_3,a_5,a_2,a_4)$ Хотя вероятность именно такого порядка такая же $\frac 1{15}$, как любого из остальных 14 возможных.
2)Запишем определенное в моем пред. посте число побед/число поражений;
$a_1\;3/0$
$a_3\;1/1$
$a_5\;0/0$
$a_4\;0/1$
$a_5\;0/2$
(порядок такой, в котором они стояли бы в "таблице неоконченного чемпионата")
Гипотеза: можно так скомпоновать "рейтинги" из чисел побед и поражений, что трудоемким подсчетом вероятностей можно не заниматься, и не использовать структуру графа при ответе в случае досрочной остановки.

[Mihaylo]

Значит предлагаете после прерывания алгоритма восстанавливать порядок элементов по таблице рейтингов?

Я вижу следующую проблему - нужно научиться рассчитывать число перестановок и вероятности для произвольного графа сравнений.