枚举二叉树的算法改进
Algorithm improvement for enumerating binary trees
目前我可以使用以下暴力 Prolog 代码枚举 rooted planar unlabeled 二叉树。
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).
然而，这是一种低效的蛮力算法。
是否有更有效的算法来枚举有根平面未标记二叉树？
注意：树可以通过使用前两次迭代的树生成，想想斐波那契数，并添加一元 b运行ch 或二元 b运行ch，但是这会导致重复的树。我自己可以做那个版本，我正在寻找的是一种算法，它可以第一次以有效的方式生成树而不会重复。
注意：二叉树也称为 binary expression tree or a K-ary tree，其中 K <=2。
补充
结果
我的 M(15) 暴力破解版用了 1 小时 27 分钟，
而 M(15) 的高效版本花费了大约 2 秒。
显然，高效的算法就是这样，效率更高，也是我问这个问题的原因。
莫茨金号码
对于有根平面未标记二叉树，具有 N 个节点的树数由 Motzkin 数给出。参见：OEIS A001006
Nodes Trees
1 1
2 1
3 2
4 4
5 9
对于有根平面未标记二叉树，具有 N 个内部节点的树的数量由加泰罗尼亚数字给出。有一种更有效的算法可以使用 Catalan 数生成有根平面二叉树。
注：
基于加泰罗尼亚数字的树的数量不有一元b运行ches并且只计算内部个节点。
同时
基于 Motzkin 数的树数 do 一元 b运行ches 和计数 all 个节点。
参见：
OEIS A000108
Catalan Numbers 汤姆·戴维斯
将 Prolog 列表元素与 Motzkin 数相关联
% M is Motzkin number, N is number of list elements passed to atomic_list_concat
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.
参考资料
Philippe Flajolet 和 Robert Sedgewick 合着的 "Analytic Combinatorics" 可能有帮助的免费 pdf 图书下载
另请参阅 Catalan 标记中的引用。
BNF
<expression> ::=
<unary expression>
| <binary expression>
| <terminal>
<unary expression> ::=
"(u" <expression> ")"
<binary expression> ::=
"(b" <expression> " " <expression> ")"
<terminal> ::=
"t"
使用 David Eisenstat 的
对我而言，将这些视为笔记或面包屑，以防我在忘记它后的许多个月内需要再次使用它。
为了测试答案，我使用 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 中我创建了一个符号 link 到 Windows Prolog 目录
$ ln -s "/mnt/c/Users/Eric/Documents/Prolog" /home/eric/Prolog
并更改为 WSL Prolog 目录
$ cd Prolog
然后开始Python3
~/Prolog$ python3
并导入 Python 代码
>>> import motzkin
和 运行 下面的子树的参数是 Motzkin 数
>>> 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)
并检查 Motzkin 号码
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()
关于重复的注释
我学习Motzkin数的方法是用笔和纸手工枚举树，然后通过在前面的树中添加一元b运行ch的方法找到重复的树M(N-1 ) 和二进制 b运行ches 到前面的 M(N-2) 树。
这棵树从 M(4) 棵树中为 M(5) 生成了两次
(b (u t) (u t))
第一个是在
上加一个一元b运行ch
(b (u t) t)
其次，将一元 b运行ch 添加到
(b t (u t))
完成此操作后，我得到了数字序列 1、2、4、9、21，我将其与 OEIS 搜索 一起使用，最上面的结果是 A001006对于 Motzkin 数。一旦我有了更大的 Motzkin 数字列表，我就使用 Prolog 代码为更大的输入值生成计数，他们都同意了。现在您可以将 OEIS 添加到您的编程工具箱中，并提供一个有效的示例来向其他人演示。
大局
如果你已经读到这里，那么你可能会发现这是一个更大问题的一部分，该问题首先在 Prolog 中构建一个系统，该系统可以使用术语重写来解决基本微积分的数学表达式，但更重要的是展示步骤采取。因此，这成为生成二进制表达式树以用作测试用例的一部分。下一步是能够单独设置一元和二元节点的数量，而不是让它们由 Motzkin 数固定。我只使用 Motzkin 数字来验证我是否正确生成了组合的子集。既然我有了它的模式，我就可以修改它以接受一个参数用于一元节点的数量，一个参数用于二进制节点。参见：
只有当我遇到困难时，我才会提出与此相关的问题，所以不要指望看到所有必要的面包屑。
序言输出
?- 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.
在Python 3:
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)
这个递归枚举过程对应于递归
M_1 = 1
M_n = M_{n-1} + sum_{i=1}^{n-2} M_i M_{n-1-i},
与 Wikipedia 中给出的递归相差一个。
除了已经发布的解决方案之外，我还想为任务提供以下 Prolog 解决方案。
首先，这里是对此类树的声明性描述：
e(number) --> [].
e(u(Arg)) --> [_], e(Arg).
e(b(Left,Right)) --> [_,_], e(Left), e(Right).
我也在用dcg。但是，我将它用于与问题不同的目的：在我的例子中，我只描述了一个列表以限制解决方案的深度。将非终结符视为说明通过应用规则将 肯定 消耗多少 "tokens"。另请注意，我使用 复合词 来自然地描述此类树。
示例查询，使用迭代加深：
?- length(Ls, _), phrase(e(E), Ls).
Ls = [],
E = number ;
Ls = [_5710],
E = u(number) ;
Ls = [_5710, _5716],
E = u(u(number)) ;
Ls = [_5710, _5716],
E = b(number, number) ;
Ls = [_5710, _5716, _5722],
E = u(u(u(number))) .
我现在可以数个解决方案如下：
es_count(M, Count) :-
length([_|Ls], M),
findall(., phrase(e(_), Ls), Sols),
length(Sols, Count).
这里还有几个解决方案：
?- length(_, M),
time(es_count(M, Count)),
portray_clause(m_count(M,Count)),
false.
% 7 inferences, 0.000 CPU in 0.000 seconds (64% CPU, 636364 Lips)
% 28 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 1120000 Lips)
m_count(1, 1).
% 29 inferences, 0.000 CPU in 0.000 seconds (31% CPU, 1318182 Lips)
m_count(2, 1).
% 33 inferences, 0.000 CPU in 0.000 seconds (76% CPU, 1736842 Lips)
m_count(3, 2).
% 41 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 1952381 Lips)
m_count(4, 4).
% 61 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 2178571 Lips)
m_count(5, 9).
% 109 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 2595238 Lips)
m_count(6, 21).
% 230 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 2948718 Lips)
m_count(7, 51).
% 538 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 3221557 Lips)
m_count(8, 127).
% 1,337 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 3293103 Lips)
m_count(9, 323).
% 3,434 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 3400000 Lips)
m_count(10, 835).
% 9,000 inferences, 0.003 CPU in 0.003 seconds (94% CPU, 3301541 Lips)
m_count(11, 2188).
% 23,908 inferences, 0.007 CPU in 0.024 seconds (31% CPU, 3300387 Lips)
m_count(12, 5798).
% 64,158 inferences, 0.019 CPU in 0.024 seconds (79% CPU, 3387792 Lips)
m_count(13, 15511).
% 173,579 inferences, 0.051 CPU in 0.062 seconds (83% CPU, 3397448 Lips)
m_count(14, 41835).
% 472,853 inferences, 0.139 CPU in 0.152 seconds (92% CPU, 3393690 Lips)
m_count(15, 113634).
Prolog 是一种很好的语言，可以根据声明性描述生成 详尽的解决方案！
按照@DavidEisenstat 的建议，在 Prolog recurrence relation 中编码：
motzkin_numbers(0, 1).
motzkin_numbers(1, 1).
motzkin_numbers(N, M) :-
N>1,
N1 is N-1,
motzkin_numbers(N1, M1),
N2 is N-2,
aggregate_all(sum(MiP), (
between(0, N2, I),
motzkin_numbers(I, M_i),
I_n1i is N-2-I,
motzkin_numbers(I_n1i, M_n1i),
MiP is M_i * M_n1i), Ms),
M is M1 + Ms.
我们得到
?- length(_,N), time(motzkin_numbers(N,M)).
...
N = 14,
M = 113634 ;
% 4 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 115724 Lips)
% 1,863,722 inferences, 1.107 CPU in 1.107 seconds (100% CPU, 1683529 Lips)
N = 15,
M = 310572 ;
% 4 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 129232 Lips)
% 4,499,430 inferences, 2.645 CPU in 2.646 seconds (100% CPU, 1700821 Lips)
N = 16,
M = 853467
...
但 SWI-Prolog 最近添加了表格：只需添加此声明
:- table motzkin_numbers/2.
我们得到
...
% 310 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 591031 Lips)
N = 14,
M = 113634 ;
% 331 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 457731 Lips)
N = 15,
M = 310572 ;
% 352 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 310880 Lips)
N = 16,
M = 853467 ;
% 373 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 703349 Lips)
N = 17,
M = 2356779 ;
...
目前我可以使用以下暴力 Prolog 代码枚举 rooted planar unlabeled 二叉树。
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).
然而，这是一种低效的蛮力算法。
是否有更有效的算法来枚举有根平面未标记二叉树？
注意：树可以通过使用前两次迭代的树生成，想想斐波那契数，并添加一元 b运行ch 或二元 b运行ch，但是这会导致重复的树。我自己可以做那个版本，我正在寻找的是一种算法，它可以第一次以有效的方式生成树而不会重复。
注意：二叉树也称为 binary expression tree or a K-ary tree，其中 K <=2。
补充
结果
我的 M(15) 暴力破解版用了 1 小时 27 分钟， 而 M(15) 的高效版本花费了大约 2 秒。
显然，高效的算法就是这样，效率更高，也是我问这个问题的原因。
莫茨金号码
对于有根平面未标记二叉树，具有 N 个节点的树数由 Motzkin 数给出。参见：OEIS A001006
Nodes Trees
1 1
2 1
3 2
4 4
5 9
对于有根平面未标记二叉树，具有 N 个内部节点的树的数量由加泰罗尼亚数字给出。有一种更有效的算法可以使用 Catalan 数生成有根平面二叉树。
注：
基于加泰罗尼亚数字的树的数量不有一元b运行ches并且只计算内部个节点。
同时
基于 Motzkin 数的树数 do 一元 b运行ches 和计数 all 个节点。
参见：
OEIS A000108
Catalan Numbers 汤姆·戴维斯
将 Prolog 列表元素与 Motzkin 数相关联
% M is Motzkin number, N is number of list elements passed to atomic_list_concat
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.
参考资料
Philippe Flajolet 和 Robert Sedgewick 合着的 "Analytic Combinatorics" 可能有帮助的免费 pdf 图书下载
另请参阅 Catalan 标记中的引用。
BNF
<expression> ::=
<unary expression>
| <binary expression>
| <terminal>
<unary expression> ::=
"(u" <expression> ")"
<binary expression> ::=
"(b" <expression> " " <expression> ")"
<terminal> ::=
"t"
使用 David Eisenstat 的
对我而言，将这些视为笔记或面包屑，以防我在忘记它后的许多个月内需要再次使用它。
为了测试答案，我使用 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 中我创建了一个符号 link 到 Windows Prolog 目录
$ ln -s "/mnt/c/Users/Eric/Documents/Prolog" /home/eric/Prolog
并更改为 WSL Prolog 目录
$ cd Prolog
然后开始Python3
~/Prolog$ python3
并导入 Python 代码
>>> import motzkin
和 运行 下面的子树的参数是 Motzkin 数
>>> 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)
并检查 Motzkin 号码
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()
关于重复的注释
我学习Motzkin数的方法是用笔和纸手工枚举树，然后通过在前面的树中添加一元b运行ch的方法找到重复的树M(N-1 ) 和二进制 b运行ches 到前面的 M(N-2) 树。
这棵树从 M(4) 棵树中为 M(5) 生成了两次
(b (u t) (u t))
第一个是在
上加一个一元b运行ch(b (u t) t)
其次，将一元 b运行ch 添加到
(b t (u t))
完成此操作后，我得到了数字序列 1、2、4、9、21，我将其与 OEIS 搜索 一起使用，最上面的结果是 A001006对于 Motzkin 数。一旦我有了更大的 Motzkin 数字列表，我就使用 Prolog 代码为更大的输入值生成计数，他们都同意了。现在您可以将 OEIS 添加到您的编程工具箱中，并提供一个有效的示例来向其他人演示。
大局
如果你已经读到这里，那么你可能会发现这是一个更大问题的一部分，该问题首先在 Prolog 中构建一个系统，该系统可以使用术语重写来解决基本微积分的数学表达式，但更重要的是展示步骤采取。因此，这成为生成二进制表达式树以用作测试用例的一部分。下一步是能够单独设置一元和二元节点的数量，而不是让它们由 Motzkin 数固定。我只使用 Motzkin 数字来验证我是否正确生成了组合的子集。既然我有了它的模式，我就可以修改它以接受一个参数用于一元节点的数量，一个参数用于二进制节点。参见：
只有当我遇到困难时，我才会提出与此相关的问题，所以不要指望看到所有必要的面包屑。
序言输出
?- 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.
在Python 3:
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)
这个递归枚举过程对应于递归
M_1 = 1
M_n = M_{n-1} + sum_{i=1}^{n-2} M_i M_{n-1-i},
与 Wikipedia 中给出的递归相差一个。
除了已经发布的解决方案之外，我还想为任务提供以下 Prolog 解决方案。
首先，这里是对此类树的声明性描述：
e(number) --> []. e(u(Arg)) --> [_], e(Arg). e(b(Left,Right)) --> [_,_], e(Left), e(Right).
我也在用dcg。但是，我将它用于与问题不同的目的：在我的例子中，我只描述了一个列表以限制解决方案的深度。将非终结符视为说明通过应用规则将 肯定 消耗多少 "tokens"。另请注意，我使用 复合词 来自然地描述此类树。
示例查询，使用迭代加深：
?- length(Ls, _), phrase(e(E), Ls). Ls = [], E = number ; Ls = [_5710], E = u(number) ; Ls = [_5710, _5716], E = u(u(number)) ; Ls = [_5710, _5716], E = b(number, number) ; Ls = [_5710, _5716, _5722], E = u(u(u(number))) .
我现在可以数个解决方案如下：
es_count(M, Count) :-
length([_|Ls], M),
findall(., phrase(e(_), Ls), Sols),
length(Sols, Count).
这里还有几个解决方案：
?- length(_, M), time(es_count(M, Count)), portray_clause(m_count(M,Count)), false. % 7 inferences, 0.000 CPU in 0.000 seconds (64% CPU, 636364 Lips) % 28 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 1120000 Lips) m_count(1, 1). % 29 inferences, 0.000 CPU in 0.000 seconds (31% CPU, 1318182 Lips) m_count(2, 1). % 33 inferences, 0.000 CPU in 0.000 seconds (76% CPU, 1736842 Lips) m_count(3, 2). % 41 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 1952381 Lips) m_count(4, 4). % 61 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 2178571 Lips) m_count(5, 9). % 109 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 2595238 Lips) m_count(6, 21). % 230 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 2948718 Lips) m_count(7, 51). % 538 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 3221557 Lips) m_count(8, 127). % 1,337 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 3293103 Lips) m_count(9, 323). % 3,434 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 3400000 Lips) m_count(10, 835). % 9,000 inferences, 0.003 CPU in 0.003 seconds (94% CPU, 3301541 Lips) m_count(11, 2188). % 23,908 inferences, 0.007 CPU in 0.024 seconds (31% CPU, 3300387 Lips) m_count(12, 5798). % 64,158 inferences, 0.019 CPU in 0.024 seconds (79% CPU, 3387792 Lips) m_count(13, 15511). % 173,579 inferences, 0.051 CPU in 0.062 seconds (83% CPU, 3397448 Lips) m_count(14, 41835). % 472,853 inferences, 0.139 CPU in 0.152 seconds (92% CPU, 3393690 Lips) m_count(15, 113634).
Prolog 是一种很好的语言，可以根据声明性描述生成 详尽的解决方案！
按照@DavidEisenstat 的建议，在 Prolog recurrence relation 中编码：
motzkin_numbers(0, 1).
motzkin_numbers(1, 1).
motzkin_numbers(N, M) :-
N>1,
N1 is N-1,
motzkin_numbers(N1, M1),
N2 is N-2,
aggregate_all(sum(MiP), (
between(0, N2, I),
motzkin_numbers(I, M_i),
I_n1i is N-2-I,
motzkin_numbers(I_n1i, M_n1i),
MiP is M_i * M_n1i), Ms),
M is M1 + Ms.
我们得到
?- length(_,N), time(motzkin_numbers(N,M)).
...
N = 14,
M = 113634 ;
% 4 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 115724 Lips)
% 1,863,722 inferences, 1.107 CPU in 1.107 seconds (100% CPU, 1683529 Lips)
N = 15,
M = 310572 ;
% 4 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 129232 Lips)
% 4,499,430 inferences, 2.645 CPU in 2.646 seconds (100% CPU, 1700821 Lips)
N = 16,
M = 853467
...
但 SWI-Prolog 最近添加了表格：只需添加此声明
:- table motzkin_numbers/2.
我们得到
...
% 310 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 591031 Lips)
N = 14,
M = 113634 ;
% 331 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 457731 Lips)
N = 15,
M = 310572 ;
% 352 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 310880 Lips)
N = 16,
M = 853467 ;
% 373 inferences, 0.001 CPU in 0.001 seconds (100% CPU, 703349 Lips)
N = 17,
M = 2356779 ;
...