Guy*_*der 5 language-agnostic algorithm binary-tree oeis motzkin-numbers
目前,我可以使用以下暴力Prolog代码枚举带根的 平面 未标记二进制树.
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).
然而,这是低效的强力算法.
是否有更有效的算法来枚举带根的平面未标记二进制树？
注意:树可以通过使用前两次迭代中的树来生成,想一想Fibonacci数,并添加一元分支或二元分支,但这会导致重复的树.我自己可以做那个版本,我正在寻找的是一种算法,它可以在没有重复的情况下以高效的方式生成树.
注意:二叉树也称为二进制表达式树或K <= 2 的K-ary树.
我对M(15)的暴力版本需要1小时27分钟,而M(15)的高效版本需要大约2秒钟.
显然,有效的算法就是这样,效率更高,为什么我问这个问题.
具有N根节点平面未标记二进制树的节点的树的数量由Motzkin数给出.见:OEIS A001006
Nodes Trees
1 1
2 1
3 2
4 4
5 9
具有N个内部节点的树的数量由带有根的平面未标记二进制树由加泰罗尼亚数字给出.有一种更有效的算法,用于使用加泰罗尼亚数生成有根平面二叉树.
注意:
基于加泰罗尼亚数字的树的数量没有一元分支,只计算内部节点.
而
基于Motzkin数字的树的数量确实有一元分支并计算所有节点.
请参阅:Tom Davis 撰写的
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的免费下载书,可能有助于Philippe Flajolet和Robert Sedgewick的"Analytic Combinatorics"
另请参阅加泰罗尼亚语标签中的参考文献.
<expression> ::=
<unary expression>
| <binary expression>
| <terminal>
<unary expression> ::=
"(u" <expression> ")"
<binary expression> ::=
"(b" <expression> " " <expression> ")"
<terminal> ::=
"t"
把这些看作是笔记或面包屑,以防万一我忘记它之后需要在几个月内再次使用它.
为了测试答案,我使用了安装了Python 3的WSL(适用于Linux的Windows子系统)
使用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 Prolog目录
$ cd Prolog
然后开始Python3
~/Prolog$ python3
并导入了Python代码
>>> import motzkin
并使用ubtrees作为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数字的方法是手工用笔和纸计算树,并通过使用向前面的树M(N-1)添加一元分支和前面的M(N)的二元分支的方法找到副本. -2)树木.
对于来自M(4)树的M(5),这一棵树被生成两次
(b (u t) (u t))
第一个通过添加一元分支
(b (u t) t)
第二个是添加一个一元的分支
(b t (u t))
在这之后,我得到了数字1,2,4,9,21的序列,我使用了 OEIS搜索,最高的结果是A001006用于Motzkin数字.一旦我有了更大的Motzkin数字列表,我使用Prolog代码生成更大输入值的计数,他们都同意了.现在,您可以使用有效示例将OEIS添加到编程工具箱中,以向其他人演示.
如果您已经阅读了这么远,那么您可能会发现这是一个更大问题的一部分,它首先在Prolog中构建一个系统,可以使用术语重写来解决基本微积分的数学表达式,但更重要的是显示所采取的步骤.因此,这将成为生成二进制表达式树的一部分,用作测试用例.下一步是能够单独设置一元和二元的节点数,而不是通过Motzkin数固定它们.我只使用Motzkin数字来验证我是否正确生成了组合的子集.现在我有了模式,我可以修改它以接受一个参数用于一元节点的数量,一个用于二进制节点.请参阅:如何使用带有CLP(FD)和多个约束的DCG枚举组合
只有当我遇到困难时,我才会问一个与此相关的问题,所以不要指望看到所有必要的面包屑.
?- 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.
除了已经发布的解决方案之外，我还想为该任务提供以下Prolog解决方案。
首先，这是对此类树的声明性描述：
e(number) --> []。 e(u(Arg)) --> [_], e(Arg)。 e(b(Left,Right)) --> [_,_], e(Left), e(Right)。
我也在使用dcg。但是，我将它用于与问题不同的目的：就我而言，我只描述了一个列表以限制解决方案的深度。将非终结符视为说明通过应用规则肯定会消耗多少“令牌” 。另请注意，我使用复合术语来自然地描述此类树。
示例查询，使用迭代深化：
?- 长度（Ls，_），短语（e（E），Ls）。 ls = [], E = 数字； Ls = [_5710], E = u(数) ; Ls = [_5710, _5716], E = u(u(数字)); Ls = [_5710, _5716], E = b(number, number) ; Ls = [_5710, _5716, _5722], E = u(u(u(number))) 。
我现在可以计算解决方案如下：
es_count(M, Count) :-
长度([_|Ls], M),
findall(., 短语(e(_), Ls), Sols),
长度（溶胶，计数）。
这里还有一些解决方案：
?- 长度(_, M), 时间（es_count（M，计数））， 描绘子句（m_count（M，Count））， 错误的。 % 7 推理，0.000 秒内 0.000 CPU（64% CPU，636364 唇） % 28 推理，0.000 秒内 0.000 CPU（81% CPU，1120000 唇） m_count(1, 1)。 % 29 推理，0.000 秒内 0.000 CPU（31% CPU，1318182 唇） m_count(2, 1)。 % 33 推理，0.000 秒内 0.000 CPU（76% CPU，1736842 唇） m_count(3, 2)。 % 41 推理，0.000 秒内 0.000 CPU（81% CPU，1952381 唇） m_count(4, 4)。 % 61 推理，0.000 秒内 0.000 CPU（88% CPU，2178571 唇） m_count(5, 9)。 % 109 推理，0.000 秒内 0.000 CPU（91% CPU，2595238 唇） m_count(6, 21)。 % 230 推理，0.000 秒内 0.000 CPU（93% CPU，2948718 唇） m_count(7, 51)。 % 538 推理，0.000 秒内 0.000 CPU（97% CPU，3221557 唇） m_count(8, 127)。 % 1,337 推理，0.000 秒内 0.000 CPU（99% CPU，3293103 唇） m_count(9, 323)。 % 3,434 推理，0.001 秒内 0.001 CPU（99% CPU，3400000 唇） m_count(10, 835)。 % 9,000 次推理，0.003 秒内 0.003 CPU（94% CPU，3301541 唇） m_count(11, 2188)。 % 23,908 推理，0.024 秒内 0.007 CPU（31% CPU，3300387 唇） m_count(12, 5798)。 % 64,158 推理，0.024 秒内 0.019 CPU（79% CPU，3387792 唇） m_count(13, 15511)。 % 173,579 推理，0.062 秒内 0.051 CPU（83% CPU，3397448 唇） m_count(14, 41835)。 % 472,853 推理，0.152 秒内 0.139 CPU（92% CPU，3393690 唇） m_count(15, 113634)。
Prolog 是一种很好的语言，用于根据声明性描述详尽地生成解决方案！
在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},
它与维基百科中给出的递归式移动了一位。