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

[Mihaylo]

Добрый день, друзья!

Благодаря iancaple удалось получить формулы для расчета числа перестановок для ряда алгоритмов сортировки. Я полностью удовлетворен полученным результатом.

Теперь у меня возникла новая задача по поводу перестановок. Нужно разработать оптимальный алгоритм сортировки. Не секрет, что в основе алгоритмов сортировки лежит операция сравнения двух элементов массива, при этом минимальное число таких сравнений для массива из $n$ чисел равно $\log_2 n$.
В каждой итерации алгоритм должен сравнить два таких элемента массива и получить такое дерево сортировки, чтобы число перестановок $PC$ на данной итерации было минимальным. То есть алгоритм должен быть жадным по этому критерию.
Учитывая, что в зависимости от значений сравниваемых чисел может получиться либо $graph_1$ ($x_1>x_2$), либо $graph_2$ ($x_2>x_1$), то число перестановок $PC$ будет случайной величиной. Следовательно минимизировать придется математическое ожидание величины $PC$. Считать, что в каждой итерации $graph_1$ и $graph_2$ равновероятны.

Изначально граф представляет собой лес из $n$ вершин, не связанных с дугами ($n$ компонент связности). Число перестановок равно $n!$.
Итерация 1. Из соображений симметрии можно взять любые два числа и сравнить. В результате получим однозначно $\frac{n!}{2}$ перестановок.
Дальнейшие итерации усложняются.
Итерация 2. У меня получилось, что все варианты сравнения дают абсолютно одинаковый результат по величине $M(PC)=\frac{n!}{4}$, но получаются графы сравнения различной структуры. Наверное алгоритм должен сделать прогноз на одну итерацию вперед...
Итерация 3. Я рассмотрел несколько вариантов выбора в итерации 2 и пришел к выводу, что многие варианты дают одинаковый результат $M(PC)=\frac{n!}{8}$, но не все. Есть исключения: например, сравниваем $x_1$ и $x_2$ в первой итерации, затем $x_3$ и $x_4$ - во второй итерации и, наконец, в третьей итерации сравниваются наибольшее число в паре $(x_1, x_2)$ с наименьшим числом в паре $(x_3, x_4)$. При таком алгоритме получается $\frac{29n!}{240}$, что меньше чем $\frac{n!}{8}$.
Итерация 4. Так как рассмотрел не все варианты в итерации 3, поэтому испытываю сложность в дальнейшем продвижении.

Нужно научиться вычислять число перестановок при произвольном графе сортировки (не только вида "дерево").

Допустим дана матрица смежности ориентированного графа. Как вычислять число перестановок?

[iancaple]

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

Нужно научиться вычислять число перестановок при произвольном графе сортировки (не только вида "дерево").

Да уж, задачка...
Есть мысль, как бороться со срастанием ветвей, пока оно не приобрело слишком массовый характер. Рассмотрим 2 регулярных дерева, сросшиеся в вершине 3. Число перестановок для этого графа на рис. $16$ А если в точку срастания переместить корень одного из деревьев, число перестановок в каждом новом, регулярном дереве $8$.

Равенство $16=8+8$ не случайно. Для каждой конкретной перестановки число в одном из корней сросшихся деревьев либо больше, либо меньше значения в другом. В каждом случае эта дополнительная информация приводит к одному из изображенных регулярных деревьев, которые и надо обсчитать отдельно, а результаты сложить.
Ничему бы не помешало наличие поддерева $C$, растущего из вершины 3.Оно так и останется при всех перемещениях расти из вершины 3. Такое поддерево нужно при разделении срастания оставлять не на том дереве, корень которого стал общим корнем, а на другом.

[Mihaylo]

iancaple писал(а):

Ничему бы не помешало наличие поддерева $C$, растущего из вершины 3.Оно так и останется при всех перемещениях расти из вершины 3. Такое поддерево нужно при разделении срастания оставлять не на том дереве, корень которого стал общим корнем, а на другом.

Кажется, Вы не правы - нужно это поддерево подвешивать к обоим деревьям.

Mihaylo писал(а):

Нужно научиться вычислять число перестановок при произвольном графе сортировки (не только вида "дерево").

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

Мне показалось, что можно попробовать доказать некоторые частные утверждения, например: "оптимальным сравнением двух чисел из разных деревьев, будет такое, когда одно число взято из корня одного дерева, а второе - из самого низкого листика второго дерева". Это утверждение будет справедливо только для деревьев (не для произвольного графа), но уже что-то.

Еще при анализе выясняется, что все построение оптимального графа сортировки крутится вокруг попытки как можно быстро построить дерево типа простая цепь ("бамбук"). Именно простая цепь дает в итоге самое наименьшее значение $PC$ на данной итерации и, в конечном итоге, простая цепь представляет искомый ответ - отсортированный массив. Но учитывая, что процесс построения графа сортировки случаен, то могут случайно получаться всякие гусеницы и даже необязательно деревья. Я к тому, что можно подоказывать какие-нибудь утверждения хотя бы относительно простой цепи.

[iancaple]

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

iancaple писал(а):

Ничему бы не помешало наличие поддерева $C$, растущего из вершины 3.Оно так и останется при всех перемещениях расти из вершины 3. Такое поддерево нужно при разделении срастания оставлять не на том дереве, корень которого стал общим корнем, а на другом.

Кажется, Вы не правы - нужно это поддерево подвешивать к обоим деревьям.

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

[Mihaylo]

Mihaylo писал(а):

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

Mihaylo писал(а):

Итерация 3. Я рассмотрел несколько вариантов выбора в итерации 2 и пришел к выводу, что многие варианты дают одинаковый результат $M(PC)=\frac{n!}{8}$, но не все. Есть исключения: например, сравниваем $x_1$ и $x_2$ в первой итерации, затем $x_3$ и $x_4$ - во второй итерации и, наконец, в третьей итерации сравниваются наибольшее число в паре $(x_1, x_2)$ с наименьшим числом в паре $(x_3, x_4)$. При таком алгоритме получается $\frac{29n!}{240}$, что меньше чем $\frac{n!}{8}$.

Ошибся в расчетах, оказалось $\frac{29n!}{240}$ - это неправда. Правильный ответ - $\frac{n!}{8}$. После этого как-то все стало понятно, природу не обманешь - математическое ожидание количества перестановок $PC$ при выборе любой пары для сравнения на любое количество итераций вперед уменьшает $PC$ в два раза на каждой прогнозируемой итерации.
Немного подумал, это ведь естественно!

Вопрос по по оптимальному алгоритму вопросу снят. Такого алгоритма не существует, то есть все алгоритмы такие.

[iancaple]

Ну а какого результата можно было ждать в таком грубом предположении?

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

минимизировать придется математическое ожидание величины $PC$. Считать, что в каждой итерации $graph_1$ и $graph_2$ равновероятны.

Это мало отличается от когда-то слышанного рассуждения: "любое событие либо будет, либо нет. Значит, его вероятность $50$%"
Могу привести по крайней мере 2 примера, когда вероятности двух исходов очередного сравнения сильно отличаются от $50$%.
В начале сортировки:В достаточно широком множестве различных элементов уже проведено 2 сравнения $a>b$, $c>d$.Сравнение $b>c$ приводит к линейному графу с числом перестановок $\frac{n!}{24}$, а сравнение $b<c$ -к N-образному графу с числом перестановок $\frac{5n!}{24}$, тогда и вероятность исхода сравнения $b>c$ в 5 раз меньше вероятности противоположного исхода.
В конце сортировки: предположим, $n-1$ элементов уже отсортированы и образуют линейный граф. Берем элемент, про который ничего пока не известно, если сравнивать его не с одним из средних, а с наименьшим, вероятность, что он меньше, $\frac 1n$, а вероятность, что он больше, $\frac{n-1}n$
Ну и понятно, что в середине сортировки могут быть такие же перекосы. Поэтому я старался решить без использования этого предположения. Энтропию $H=\log_2(PC)$ отслеживать, количество информации. Какое-нибудь утверждение доказать типа "при любом графе уже проведенных сравнений найдутся два элемента, сравнение которых даст количество информации не менее данной константы $\alpha$ бит, $0<\alpha <1$"

[Mihaylo]

iancaple писал(а):

Могу привести по крайней мере 2 примера, когда вероятности двух исходов очередного сравнения сильно отличаются от $50$%.

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

iancaple писал(а):

Сравнение $b>c$ приводит к линейному графу с числом перестановок $\frac{n!}{24}$, а сравнение $b<c$ -к N-образному графу с числом перестановок $\frac{5n!}{24}$, тогда и вероятность исхода сравнения $b>c$ в 5 раз меньше вероятности противоположного исхода.

$M(PC)=\frac{1}{2}\cdot\frac{n!}{24}+\frac{1}{2}\cdot\frac{5n!}{24}=\frac{n!}{8}$
На третьей итерации все варианты выбора дают такой результат.

-- 29.08.2015, 06:12 --

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

[iancaple]

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

$M(PC)=\frac{1}{2}\cdot\frac{n!}{24}+\frac{1}{2}\cdot\frac{5n!}{24}=\frac{n!}{8}$

Нет. Я выше нашел вероятности исходов сравнений. $M(PC)=\frac{1}{6}\cdot\frac{n!}{24}+\frac{5}{6}\cdot\frac{5n!}{24}=\frac{13n!}{72}$
У Вас как бы в модель заложено, что вероятности ответов равны и каждый ответ приносит полноценный 1 бит информации. Тогда за $\log_2(n!)$ сравнений энтропию ансамбля обнулите (что с нецелостью этого числа делать-то?), то есть ансамбль отсортирован, и зачем тогда изобретено столько алгоритмов сортировки.
А на самом деле 1 бит это редкая удача, например, данный пост это 0 бит, т.к. все и раньше было ясно.

[Mihaylo]

iancaple в сообщении #1048824 писал(а):

тогда и вероятность исхода сравнения $b>c$ в 5 раз меньше вероятности противоположного исхода.

Я вот этот момент не понял.

-- 29.08.2015, 12:10 --

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

[Mihaylo]

Ага, значит я неправильно выбрал элементарные события при расчете вероятности.

[iancaple]

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

iancaple в сообщении #1048824 писал(а):

тогда и вероятность исхода сравнения $b>c$ в 5 раз меньше вероятности противоположного исхода.

Я вот этот момент не понял.

А между тем это просто классическое определение вероятности. Элементарные события -это перестановки, удовлетворяющие двум уже сделанным сравнениям, их $\frac{n!}4$, анализом графа установлено, что событию $b>c$ благоприятствуют в 5 раз меньше эл.событий, чем противоположному.
Ну Вы уже разобрались. Все равно надо создавать какую-то общую базу согласованных утверждений.

[Mihaylo]

Ясно, полное пространство элементарных событий имеет размер $n!$.

Получается на каждой итерации мы имеем:
$M(PC)=\frac{PC_1}{PC_1+PC_2}\cdot PC_1+\frac{PC_2}{PC_1+PC_2}\cdot PC_2$,
где $PC_1$ и $PC_2$ - число перестановок при разных исходах сравнения; $PC_1+PC_2=PC_0$, где $PC_0$ - фактическое число перестановок в текущей итерации.
$M(PC)=PC_1+PC_2-\frac{2\cdot PC_1\cdot PC_2}{PC_1+PC_2}$

[Mihaylo]

Если я все правильно рассчитываю, то дальнейшие рассуждения таковы:
$M(PC)=PC_0-\frac{2\cdot PC_1\cdot PC_2}{PC_0}$
принимает минимальное значение при
$PC_1\cdot PC_2 = \max$

Поитерационный расчет показывает, что первые $\left\lfloor\frac{n}{2}\right\rfloor$ итераций алгоритм должен сравнивать числа попарно, вовлекая в сравнение каждый раз новые числа, строя лес из "палочек". Очень смахивает на реализацию принципа "разделяй и властвуй".

Гораздо более интересное начинается после попарных сравнений (после $\left\lfloor\frac{n}{2}\right\rfloor$ итераций). Количество и разнообразие вариаций резко возрастает.

-- 29.08.2015, 20:34 --

Дальше трудно из-за витиеватости отдельных графов.

Вот хотя бы $PC$ вот этого графа как посчитать?

[Mihaylo]

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

Постепенно (пока бездоказательно) прихожу к выводу, что в последующих $\left\lfloor\frac{n}{4}\right\rfloor$ итераций должны сравниваться попарно "палочки" по принципу "наибольший сравнивается с наибольшим" или "наименьший - с наименьшим".

[iancaple]

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

Постепенно (пока бездоказательно) прихожу к выводу, что в последующих $\left\lfloor\frac{n}{4}\right\rfloor$ итераций должны сравниваться попарно "палочки" по принципу "наибольший сравнивается с наибольшим" или "наименьший - с наименьшим".

Почему бездоказательно? Это очевидно, из симметрии возможных исходов вероятность каждого исхода $\frac 12$, отсюда и минимум $M(PC)$ и максимум информации от сравнения 1 бит. Более того, если $n=2^k$-степень двойки, то симметрию в сравнении корней можно сохранить для первых $2^{k-1}+2^{k-2}+...+1=n-1$ итераций, и это хорошо тем, что итогом станет единое регулярное "без срастаний" дерево, с которым нам легче обращаться. Предложите алгоритм, в каком порядке будет уменьшаться ветвление и увеличиваться длина дерева, пока не придем к линейному графу.