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

[Mihaylo]

А, кажется наконец-то я сейчас понял Вашу идею. На интуитивном уровне у меня тоже такая была.

То есть рейтинги вершин позволяют выбрать наилучшие вершины для сравнения. В рассматриваемом случае наилучшими были 0/0 и 1/1 - такое сравнение достаточно неопределенное, а значит дает большое количество информации. Так?

[iancaple]

Так.
В ответ на Ваш предыдущий вопрос я могу подобраться к расчету числа перестановок, удовлетворяющих системе образующих неравенств в виде дерева+одно срастание ветвей, только боюсь, формулы будут очень громоздкие. Но то, что страшно для человека, бывает нестрашно для машины, и наоборот.
Пусть $A$-дерево с корнем $a$ и одним из листов $b$, $B$- другое дерево с корнем. Назовем $AB$ дерево, получающееся после размещения корня $B$ в вершине $b$. Как и раньше, $T_x$-поддерево с корнем $x$, $|T_x|$- число вершин в нем.$|AB|=|A|+|B|-1$ (никто не пугайтесь, АВ-это просто имя переменной, как и РС, например)
В соответствии с принятым ранее порядком, наименьший элемент стоит в корне, далее стрелки по возрастанию. Обозначим $y><a$, когда элементы несравнимы по дереву (неизвестно, который меньше).
Имеем

$$PC(A)=\frac{|A|!}{\prod_{x\in A}|T_x|}=\frac{|A|!}{\prod_{y><b}|T_y|\prod_{x<b}|T_x|}$$

$$PC(AB)=\frac{(|A|+|B|-1)!}{\prod_{y><b}|T_y|\prod_{x<b}(|T_x|+|B|-1)\prod_{z\in B}|T_z|}=PC(A)PC(B)\frac{(|A|+|B|-1)!}{|A|!|B|!}\prod_{x<b}\frac{|T_x|}{|T_x|+|B|-1}$$

И это только лемма была

[Mihaylo]

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

[Mihaylo]

Может рассматривать граф как совокупность простых цепей или даже лучше как совокупность деревьев?

[iancaple]

Совокупностью каких деревьев является у Вас орграф с ребрами $(1,2),(1,3),(4,3)$ ?

[Mihaylo]

Подход к разработке алгоритмов, жадных по негэнтропии, случайно попался в книжке Рассела С., Норвига П. Искусственный интеллект. Современный подход. 2006. (Глава 18. Обучение на основе наблюдений. Параграф "Выбор проверок атрибутов". Страница 877.) На самом деле целью параграфа является не разработка оптимальных алгоритмов, а оптимальный выбор атрибута для классификации данных. Суть та же: выбираем элементы данных, операция над которыми даст наибольшее уменьшение энтропии задачи.

Несколько забросил тему, надо бы вернуться.
Метод разработки алгоритмов, жадных по негэнтропии, весьма интересен. Ведь его можно применить не только к сортировке массивов. Метод применим к любой задаче, в которой исходные данные представлены в виде массива некоторой размерности.
Взять, например, задачу поиска наикратчайшего пути... Жадность по энтропии в этой задаче - это (фактически) желание найти наикратчайший путь, пройдя минимум дорог.
Метод не применим к задачам, в которых имеется неснимаемая неопределенность (например, шахматы). Задача должна иметь условие, которое полностью и однозначно определяет решение. К таким задачам, в частности, по определению относятся задачи класса $P$ и соответственно класса $NP$.

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

[Mihaylo]

iancaple, в задаче сортировки получается так: множество графов сортировки замкнуто относительно операции сравнения. Что это за алгебраическая система? (Я основы алгебры еще не изучил. )
Какие еще простые замкнутые алгебраические системы можно придумать, пригодные для задачи сортировки?

[iancaple]

Стремление свести к задаче алгебры -оно понятно. Как-то давно заметил -если какой-то факт имеет два доказательства, средствами алгебры и средствами другой дисциплины - то средствами алгебры оно и проще и красивее.
Но что есть операция и где она замкнута? Операций сравнения много, как и пар вершин графа. Исходов применения любой из них не один, а три :1)операция не дает новой информации и не изменяет, значит, граф; 2) $a>b$ и появляется новое ребро; 3)$b>a$ и тоже.

[Mihaylo]

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

Но что есть операция и где она замкнута?

Поясню: у нас имеется $n$ исходных графов-вершин. Сравнивать можно любые две вершины из входного множества графов, но мы все равно будем получать множество графов. Таким образом множества графов замкнуто относительно операции сравнения. (Получение новой информации тут даже не при чем. Речь только об алгебраическом преобразовании.)

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

[iancaple]

Повторю вопрос: операции сравнения какого элемента с каким, и с каким исходом сравнения? Сколько, значит, существует оепераций сравнения? А Вы пишете: операцИЯ

[Mihaylo]

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

А Вы пишете: операцИЯ

Мы, кажется, на разных языках говорим. Все потому, что не на математическом!

Для меня операция сравнения - это бинарная операция $g=C(s_1,s_2)$, где $s_1, s_2$ - это произвольные вершины (элементы массива), $g$ - это направленная дуга между вершинами. Ну как бы эту операцию достаточно один раз определить, поэтому она одна.

Правильнее записать так: $G_i=C(S_1(G_{i-1}), S_2(G_{i-1}), G_{i-1})$, где $G_{i-1}$ - исходный граф, $G_i$ - результат, $S_1, S_2$ - это операции выбора вершин (произвольные), $C$ - операция сравнения вершин, которая достраивает граф $G_{i-1}$ до графа $G_i$ путем добавления одной дуги, $i$ - номер итерации.

Аналогично говорят про операцИЮ сложения и умножения в коммутативных кольцах, полях.

[iancaple]

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

Правильнее записать так: $G_i=C(S_1(G_{i-1}), S_2(G_{i-1}), G_{i-1})$, где $G_{i-1}$ - исходный граф, $G_i$ - результат

Так тогда это одноместная операция на множестве графов, а не двухместная.

(Оффтоп)

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

[Mihaylo]

(Оффтоп)

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

Что касается жадного алгоритма сортировки, то, мне кажется, нужно разобраться с алгоритмом, который по утверждению энциклопедии Дональда Кнута является лучшим известным таким алгоритмом (метод бинарных вставок).
Нашел псевдокод в интернете. Метод бинарных вставок - это модификация одного из самых элементарнейших алгоритмов сортировки - метода [простых] вставок:

for  i:= 2  to  n  do   
    if  a[i-1]>a[i]  then  
    begin
        x:= a[i];  
        left:= 1;   
        right:= i-1;  
        repeat    
            sred:= (left+right) div 2;    
            if  a[sred]<x  then  
               left:= sred+1  
               else  right:= sred-1;      
         until  left>right;
         for j:=i-1 downto left  do
             a[j+1]:= a[j];  
         a[left]:= x;
    end;

Надо убедиться, что он действительно хорош...

[Mihaylo]

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

[Mihaylo]

Д.Э.Кнут писал(а):

В общем случае сортировка посредством вставок и слияния для $n$ элементов выглядит следующим образом.

i) Сравнить $\left\lfloor \frac{n}{2} \right\rfloor$ непересекающихся пар элементов. (Если $n$ нечетно, то один элемент не участвует в сравнениях.)

ii) Рассортировать $\left\lfloor \frac{n}{2} \right\rfloor$ бОльших элементов пар, найденных в шаге (i), посредством вставок и слияния.

iii) Для элементов введем обозначения $a_1, a_2, ..., a_{\left\lfloor \frac{n}{2} \right\rfloor}, b_1, b_2, ..., b_{\left\lfloor \frac{n}{2} \right\rfloor}$, где $a_1 \leqslant a_2 \leqslant ... \leqslant a_{\left\lfloor \frac{n}{2} \right\rfloor}$ и $b_i \leqslant a_i$ при $1\leqslant i \leqslant \left\lfloor \frac{n}{2} \right\rfloor$; назовем $b_1$ и все элементы $a$ главной цепочкой. Не трогая элементов $b_j$ при $j>\left\lceil \frac{n}{2} \right\rceil$, вставим посредством бинарных вставок в главную цепочку остальные элементы $b$ в следующем порядке:

$b_3, b_2; b_5,b_4;b_{11},b_{10},...,b_6;...;b_{t_k}, b_{t_k-1},...,b_{t_{k-1}+1};... \quad\quad\quad\quad\quad\quad(11)$

Наша цель - сформировать последовательность $(t_1, t_2, t_3, t_4,...)=(1,3,5,11,...)$, присутствующую в (11) таким образом, чтобы каждый из элементов $b_{t_k}, b_{t_k-1},...,b_{t_{k-1}+1}$ можно было вставить в главную цепочку не более чем за $k$ сравнений.
...

Итак, алгоритм посредством вставок и слияний за первые $(n-1)$ сравнений формирует то же самое оптимальное дерево сравнений, что и у алгоритма ENTROPY-SORT. Алгоритм работает рекурсивно (на шаге (ii) алгоритм вызывает сам себя). Шаг (iii) начинает работать только после того как сформировалось оптимальное дерево и сначала на этом шаге сортируются $b_i$ на верхушке этого дерева, далее сортировка методом бинарных вставок должна спускаться вниз по дереву. Надо разбираться, что из этого выходит...