Возможное количество деревьев двоичного поиска, которые могут быть созданы с ключами N, дано Энным каталонским числом. Почему?
В целом я нахожу, что легче использовать флаги (по крайней мере, легче помнить как), как re.I при компиляции шаблонов, чем использовать флаги встраивают.
>>> foo_pat = re.compile('foo',re.I)
>>> foo_pat.findall('some string FoO bar')
['FoO']
по сравнению с
>>> re.findall('(?i)foo','some string FoO bar')
['FoO']
3 ответа
Поскольку в статье в Википедии, на которую вы ссылались, есть четыре доказательства , похоже, вы не ищете математического объяснения соответствия между каталонскими числами и перестановками двоичное дерево.
Итак, вместо этого, вот два способа попробовать и интуитивно визуализировать, как каталонская последовательность (1, 2, 5, 14, 42, ...) возникает в комбинаторных системах.
Разделение многоугольников на треугольники
Для многоугольника со стороной N , сколькими способами вы можете провести разрезы между вершинами, которые полностью разбивают многоугольник на треугольники?
- Треугольник (N = 3): 1 (Это уже треугольник)
- Квадрат (N = 4): 2 (Можно разрезать по любой диагонали)
- Пентагон (N = 5): 5 (Две линии разреза, исходящие из вершины. Пять вершин на выбор)
- Шестиугольник (N = 6): 14 (Попробуйте нарисовать)
- ...и т. д.
Построение пути через сетку без пересечения диагонали
В этом случае количество уникальных путей - это каталонское число.
Сетка 2x2 => 2 пути
_| |
_| __|
Сетка 3x3 => 5 путей
_| | _| | |
_| _ _| | _| |
_| _| _ _| _ _| _ _ _|
4x4 сетка => 14 путей
Сетка 5x5 => 42 пути
и т. Д.
Если вы попытаетесь нарисовать возможные бинарные деревья для данного N, вы увидите, что способ перестановки деревьев такой же.
Ваше желание не просто слепо принимать соответствие между деревом и последовательностью достойно восхищения. К сожалению, трудно продвинуться дальше в этом обсуждении (и объяснить, почему каталонская формула «оказывается» такой, какая она есть), не прибегая к биномиальной математике. Обсуждение в Википедии биномиальных коэффициентов является хорошей отправной точкой, если вы хотите глубже понять комбинаторику (которая включает подсчет перестановок ).
каталонский http: / /www.nohre.se/publicImages/catalan.png
Любое двоичное дерево поиска можно закодировать, предварительно посетив все узлы и закодировав 1 для каждого родителя и 0 для каждого листа. Если у дерева n родителей, у него будет n + 1 лист, и, следовательно, двоичный код будет иметь n 1: s и (n + 1) 0: s. Более того, и любой префикс кода будет иметь не меньше 1: s, чем 0: s. Следовательно, количество возможных деревьев равно количеству путей ниже диагонали.
Вот рекурсивное решение для подсчета деревьев ...
int countTrees(int numkeys){
if(numkeys > 1){
int i =1;
int sum=0;
for(i = 1; i <= numkeys; i++){
int lcount = countTrees(i-1);
int rcount = countTrees(numkeys-i);
sum += lcount*rcount;
}
return(sum);
}else
return(1);
}