Улучшение алгоритма для перечисления двоичных деревьев
В настоящее время я могу перечислить Коренится Планарной Немеченый бинарные деревья, использующие следующий код Prolo
e --> u | b | t.
u --> ['[op(u),['], e, [']]'].
b --> ['[op(b),['], e, [','], e, [']]'].
t --> ['number(n)'].
Примечание: см. Выходные листинги ниже.
и выводить их в увеличенном размере, используя
es(S) :-
length(Ls, _),
phrase(e, Ls), % or e(Ls,[]),
atomic_list_concat(Ls,S).
Однако это неэффективный алгоритм перебора.
Есть ли более эффективный алгоритм для перечисления корневых плоских немеченых бинарных деревьев?
Примечание: деревья могут быть сгенерированы с помощью деревьев из предыдущих двух итераций, подумайте о числах Фибоначчи и добавив либо унарную ветвь, либо бинарную ветвь, однако это приводит к дублированию деревьев. Я сам мог сделать эту версию, и я искал алгоритм, который эффективно генерирует деревья с первого раза без дубликатов.
Примечание: двоичное дерево также известно как двоичное дерево выражений или К-арое дерево с К <= 2.
ДополнениеПолученные результатМоя версия грубой силы для M (15) заняла 1 час 27 минут, а эффективная версия для M (15) - около 2 секунд.
Очевидно, что эффективный алгоритм гораздо эффективнее, и поэтому я задал вопрос.
Числа Моцкина Количество деревьев сN
узлы для корневых плоских немеченых бинарных деревьев задаются числами Моцкина. Смотрите: OEIS A001006
Nodes Trees
1 1
2 1
3 2
4 4
5 9
Количество деревьев, имеющих N внутренних узлов для корневого планарного бинарного дерева без меток, задается каталонскими числами. Существует более эффективный алгоритм генерации корневых бинарных деревьев с использованием каталонских чисел.
Заметка
Количество деревьев на основе каталонских чисел делаютн имеют одинарные ветви и считают только Внутренняя узлы.
в то время ка
количество деревьев по числам Моцкинаделат имеют одинарные ветви и считаютвс узлы.
Видеть
OEIS A000108
Каталонские номера Том Дэвис
% M is Motzkin number, N is number of list elements passed to atomic_list_concat\2
m_to_n(1,1).
m_to_n(2,3).
m_to_n(M,N) :-
M > 2,
N is (M*2)-1.
es_m(M,S) :-
m_to_n(M,N),
length(Ls,N),
e(Ls,[]),
atomic_list_concat(Ls,S).
Статистика с неэффективной грубой силойes_c(M,Count) :-
aggregate_all(count, es_m(M,_), Count).
?- time(es_c(1,Count)).
% 57 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 1.
?- time(es_c(2,Count)).
% 141 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 1.
?- time(es_c(3,Count)).
% 571 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 2.
?- time(es_c(4,Count)).
% 2,740 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 4.
?- time(es_c(5,Count)).
% 13,780 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
Count = 9.
?- time(es_c(6,Count)).
% 70,072 inferences, 0.000 CPU in 0.002 seconds (0% CPU, Infinite Lips)
Count = 21.
?- time(es_c(7,Count)).
% 357,358 inferences, 0.016 CPU in 0.012 seconds (136% CPU, 22870912 Lips)
Count = 51.
?- time(es_c(8,Count)).
% 1,824,082 inferences, 0.063 CPU in 0.056 seconds (111% CPU, 29185312 Lips)
Count = 127.
?- time(es_c(9,Count)).
% 9,313,720 inferences, 0.297 CPU in 0.290 seconds (102% CPU, 31372531 Lips)
Count = 323.
?- time(es_c(10,Count)).
% 47,561,878 inferences, 1.469 CPU in 1.467 seconds (100% CPU, 32382555 Lips)
Count = 835.
?- time(es_c(11,Count)).
% 242,896,160 inferences, 7.672 CPU in 7.665 seconds (100% CPU, 31660599 Lips)
Count = 2188.
?- time(es_c(12,Count)).
% 1,240,493,974 inferences, 38.797 CPU in 38.841 seconds (100% CPU, 31974069 Lips)
Count = 5798.
?- time(es_c(13,Count)).
% 6,335,410,822 inferences, 206.047 CPU in 213.116 seconds (97% CPU, 30747425 Lips)
Count = 15511.
?- time(es_c(14,Count)).
% 32,356,235,848 inferences, 1016.156 CPU in 1018.955 seconds (100% CPU, 31841792 Lips)
Count = 41835.
?- time(es_c(15,Count)).
% 165,250,501,417 inferences, 5231.766 CPU in 5268.363 seconds (99% CPU, 31585991 Lips)
Count = 113634.
СсылкБесплатная загружаемая книга в формате PDF, которая может помочь: "Аналитическая комбинаторика" Филиппом Флажоле и Робертом Седжвиком
Также смотрите ссылки в Каталонский тег
BNF<expression> ::=
<unary expression>
| <binary expression>
| <terminal>
<unary expression> ::=
"(u" <expression> ")"
<binary expression> ::=
"(b" <expression> " " <expression> ")"
<terminal> ::=
"t"
С помощьюотве Дэвид ЭйзенстатПодумайте об этом, как о записках или панировочных сухарях, на случай, если мне понадобится использовать это снова через много месяцев после того, как я забуду эт
Чтобы проверить ответ, который я использовал WSL (Подсистема Windows для Linux) с установленным Python 3
Используя Windows 10, я создал файл с именемmotzkin.py
в каталоге
C:\Users\Eric\Documents\Prolog
с кодом Python
def ubtrees(n):
if n == 1:
yield 't'
elif n > 1:
for t in ubtrees(n - 1):
yield '(u {})'.format(t)
for i in range(1, n - 1):
for t1 in ubtrees(i):
for t2 in ubtrees(n - 1 - i):
yield '(b {} {})'.format(t1, t2)
затем в WSL я создал символическую ссылку на каталог Windows Prolog
$ ln -s "/mnt/c/Users/Eric/Documents/Prolog" /home/eric/Prolog
и перешел в каталог Пролог WSL
$ cd Prolog
затем запустил Python3
~/Prolog$ python3
и импортировал код Python
>>> import motzkin
и запустил следующее с аргументом, что ubtree - число Моцкина
>>> for value in ubtrees(1):
... print(value)
...
t
>>> for value in ubtrees(2):
... print(value)
...
(u t)
>>> for value in ubtrees(3):
... print(value)
...
(u (u t))
(b t t)
>>> for value in ubtrees(4):
... print(value)
...
(u (u (u t)))
(u (b t t))
(b t (u t))
(b (u t) t)
>>> for value in ubtrees(5):
... print(value)
...
(u (u (u (u t))))
(u (u (b t t)))
(u (b t (u t)))
(u (b (u t) t))
(b t (u (u t)))
(b t (b t t))
(b (u t) (u t))
(b (u (u t)) t)
(b (b t t) t)
и проверить числа Моцкина
def m_count(m):
count = sum(1 for x in ubtrees(m))
print("Count: ", count)
>>> m_count(1)
Count: 1
>>> m_count(2)
Count: 1
>>> m_count(3)
Count: 2
>>> m_count(4)
Count: 4
>>> m_count(5)
Count: 9
>>> m_count(6)
Count: 21
>>> m_count(7)
Count: 51
>>> m_count(8)
Count: 127
>>> m_count(9)
Count: 323
>>> m_count(10)
Count: 835
>>> m_count(11)
Count: 2188
>>> m_count(12)
Count: 5798
>>> m_count(13)
Count: 15511
>>> m_count(14)
Count: 41835
>>> m_count(15)
Count: 113634
Для выхода из интерактивного использования Python
quit()
Примечания к дубликатамТо, как я узнал о числах Моцкина, было вручную перечислять деревья ручкой и бумагой и находить дубликаты, используя метод добавления унарной ветви к предыдущим деревьям M (N-1) и двоичных ветвей к предыдущей предшествующей M ( N-2) деревья.
Это одно дерево было сгенерировано дважды для M (5) из M (4) деревьев
(b (u t) (u t))
первый, добавив унарную ветвь к
(b (u t) t)
а во-вторых, добавив унарную ветвь к
(b t (u t))
После этого у меня была последовательность чисел 1,2,4,9,21, которую я использовал с OEIS поиск и лучший результат был A001006 для чисел Моцкина. Получив больший список чисел Моцкина, я использовал код Пролога, чтобы сгенерировать счетчики для больших входных значений, и они все согласились. Теперь вы можете добавить OEIS в свой инструментарий программирования с действительным примером для демонстрации другим.
Большая картинаЕсли вы читали это далеко, то, вероятно, видите, что это является частью более серьезной проблемы, которая заключается в создании системы сначала в Прологе, которая может использовать переписывание терминов для решения математических выражений вплоть до базового исчисления, но, что более важно, показывает предпринятые шаги. Таким образом, это дает одну часть пути к созданию деревьев двоичных выражений, которые будут использоваться в качестве тестовых случаев. Следующим шагом будет возможность индивидуально установить число унарных и двоичных узлов вместо того, чтобы фиксировать их по числу Моцкина. Я использовал только числа Моцкина, чтобы убедиться, что я правильно генерировал подмножество комбинаций. Теперь, когда у меня есть шаблон для этого, я могу изменить его так, чтобы он принимал один аргумент для числа унарных узлов и один для двоичных узлов. Видеть: Как перечислить комбинации с использованием DCG с CLP (FD) и несколькими ограничениями
Только когда я застряну, я задам вопросы, связанные с этим, поэтому не ожидайте увидеть все необходимые хлебные крошки.
Пролог выходной?- length(Ls, N), phrase(e, Ls).
Ls = ['number(0)'],
N = 1 ;
Ls = ['[op(u),[', 'number(0)', ']]'],
N = 3 ;
Ls = ['[op(u),[', '[op(u),[', 'number(0)', ']]', ']]'],
N = 5 ;
Ls = ['[op(b),[', 'number(0)', ',', 'number(0)', ']]'],
N = 5 ;
Ls = ['[op(u),[', '[op(u),[', '[op(u),[', 'number(0)', ']]', ']]', ']]'],
N = 7 ;
Ls = ['[op(u),[', '[op(b),[', 'number(0)', ',', 'number(0)', ']]', ']]'],
N = 7 ;
Ls = ['[op(b),[', '[op(u),[', 'number(0)', ']]', ',', 'number(0)', ']]'],
N = 7 ;
Ls = ['[op(b),[', 'number(0)', ',', '[op(u),[', 'number(0)', ']]', ']]'],
N = 7 ;
?- es(S).
S = 'number(0)' ;
S = '[op(u),[number(0)]]' ;
S = '[op(u),[[op(u),[number(0)]]]]' ;
S = '[op(b),[number(0),number(0)]]' ;
S = '[op(u),[[op(u),[[op(u),[number(0)]]]]]]' ;
S = '[op(u),[[op(b),[number(0),number(0)]]]]' ;
S = '[op(b),[[op(u),[number(0)]],number(0)]]' ;
S = '[op(b),[number(0),[op(u),[number(0)]]]]' ;
S = '[op(u),[[op(u),[[op(u),[[op(u),[number(0)]]]]]]]]' ;
S = '[op(u),[[op(u),[[op(b),[number(0),number(0)]]]]]]' ;
S = '[op(u),[[op(b),[[op(u),[number(0)]],number(0)]]]]' ;
S = '[op(u),[[op(b),[number(0),[op(u),[number(0)]]]]]]' ;
S = '[op(b),[[op(u),[[op(u),[number(0)]]]],number(0)]]' ;
S = '[op(b),[[op(u),[number(0)]],[op(u),[number(0)]]]]' ;
S = '[op(b),[[op(b),[number(0),number(0)]],number(0)]]' ;
S = '[op(b),[number(0),[op(u),[[op(u),[number(0)]]]]]]' ;
S = '[op(b),[number(0),[op(b),[number(0),number(0)]]]]' ;
?- es_m(1,E).
E = 'number(n)' ;
false.
?- es_m(2,E).
E = '[op(u),[number(n)]]' ;
false.
?- es_m(3,E).
E = '[op(u),[[op(u),[number(n)]]]]' ;
E = '[op(b),[number(n),number(n)]]' ;
false.
?- es_m(4,E).
E = '[op(u),[[op(u),[[op(u),[number(n)]]]]]]' ;
E = '[op(u),[[op(b),[number(n),number(n)]]]]' ;
E = '[op(b),[[op(u),[number(n)]],number(n)]]' ;
E = '[op(b),[number(n),[op(u),[number(n)]]]]' ;
false.
?- es_m(5,E).
E = '[op(u),[[op(u),[[op(u),[[op(u),[number(n)]]]]]]]]' ;
E = '[op(u),[[op(u),[[op(b),[number(n),number(n)]]]]]]' ;
E = '[op(u),[[op(b),[[op(u),[number(n)]],number(n)]]]]' ;
E = '[op(u),[[op(b),[number(n),[op(u),[number(n)]]]]]]' ;
E = '[op(b),[[op(u),[[op(u),[number(n)]]]],number(n)]]' ;
E = '[op(b),[[op(u),[number(n)]],[op(u),[number(n)]]]]' ;
E = '[op(b),[[op(b),[number(n),number(n)]],number(n)]]' ;
E = '[op(b),[number(n),[op(u),[[op(u),[number(n)]]]]]]' ;
E = '[op(b),[number(n),[op(b),[number(n),number(n)]]]]' ;
false.