目前我可以使用以下蛮力prolog code列举生根的平面未标记的二进制树。
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).
但是，这是效率低下的蛮力算法。
是否有更有效的算法用于枚举生根的平面未标记的二进制树？
注意：可以通过使用前两个迭代中的树生成树，考虑斐波那契数字，并添加一单元分支或二进制分支，但这会导致重复的树。我本人可以做那个版本，我正在寻找的是一种算法，该算法是第一次以有效的方式生成树木的算法。
注意：二进制树也称为二进制表达树或带有k＆lt; = 2的k-ary树。
补充
结果
我的蛮力版本（15）花了1小时和27分钟，而M（15）的高效版本大约需要2秒。
显然，有效的算法就是这样，更有效，为什么我问了这个问题。
motzkin数字
含有 N节点的树的数量由motzkin数字提供了无标记的二进制树。请参阅：OEIS A001006
Nodes Trees
1 1
2 1
3 2
4 4
5 9
加泰罗尼亚州数字给出了具有扎根平面未标记的二进制树的内部节点的树数。有一种更有效的算法，用于使用加泰罗尼亚的数字生成扎根的平面二进制树。
注意：
基于加泰罗尼亚数字的树木数不有一单元分支，并且仅计数内部 nodes。
而
基于motzkin号码的树数 do 有一单分支，并且计数 able nodes。
请参阅：
OEIS A000108
汤姆·戴维斯（Tom Davis）的加泰罗尼亚人数
将序言列表元素与motzkin编号
% M is Motzkin number, N is number of list elements passed to atomic_list_concat2
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
的"分析组合"还请参见加泰罗尼亚标签中的参考。
motzkin数字
BNF
<expression> ::=
<unary expression>
| <binary expression>
| <terminal>
<unary expression> ::=
"(u" <expression> ")"
<binary expression> ::=
"(b" <expression> " " <expression> ")"
<terminal> ::=
"t"
使用David Eisenstat的答案
对我来说，将这些视为笔记或面包屑，以防万一我忘记了它的数月后需要再次使用它。
要测试我使用python 3安装的WSL（Linux的Windows子系统）的答案
使用Windows 10我在目录中创建了一个名为motzkin.py的文件
C:UsersEricDocumentsProlog
使用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 Directory
$ ln -s "/mnt/c/Users/Eric/Documents/Prolog" /home/eric/Prolog
并更改为WSL Prolog Directory
$ 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搜索中使用了，最高结果是Motzkin数字的A001006。一旦我拥有较大的Motzkin数字列表，我就会使用Prolog代码来生成较大输入值的计数，并且它们都同意。现在，您可以将OEI添加到编程工具框中，并有一个有效的示例向他人演示。
更大的图片
如果您已经阅读了这么远，那么您可能会发现这是一个更大的问题的一部分，该问题是在Prolog中首先构建一个系统，该系统可以使用术语重写将数学表达式求解到基本的微积分，但更重要的是显示所采取的步骤。因此，这获得了生成用作测试用例的二进制表达树的一部分。下一步是能够单独设置一元和二进制的节点的数量，而不是让它们由Motzkin编号固定。我只使用Motzkin数字来验证我正确生成了组合的子集。现在，我已经有了模式，我可以将其修改以接受一个关于单位节点数量的参数，而对于二进制节点的数量。请参阅：如何使用与CLP（FD）和多个约束的DCG列举组合
只有当我被卡住时，我才会问一个与此有关的问题，所以不要期望看到所有必要的面包屑。
prolog output
?- 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（数字） - ＆gt;[]。e（u（arg）） - ＆gt;[_]，E（arg）。e（b（左，右）） - ＆gt;[_，_]，E（左），E（右）。
我也在使用DCG。但是，我将其用于与nbsp;的问题不同的目的：在我的情况下，我仅描述一个列表，以限制解决方案的深度。认为非终端是指出有多少个"代币"将通过应用A'规则来消耗多少。还请注意，我正在使用 compound＆nbsp;术语自然描述了这种＆nbsp; trees。
示例查询，使用迭代加深：
？ - 长度（ls，_），短语（e（e），ls）。ls = []，E =数字;ls = [_5710]，e = u（数字）;ls = [_5710，_5716]，e = u（u（number））;ls = [_5710，_5716]，e = b（数字，数字）;ls = [_5710，_5716，_5722]，e = u（u（u（number）））。
我现在可以 count 解决方案如下：
es_count（m，count）： - 长度（[_ | ls]，m）， findall（。，短语（e（_），ls），sols）， 长度（溶胶，计数）。
这里还有一些解决方案：
？ - 长度（_，m）， 时间（es_count（m，count））， portray_clause（m_count（m，count））， 错误。％7推论，0.000秒内0.000 CPU（64％CPU，636364 LIPS）％28推论，0.000秒内0.000 CPU（81％CPU，1120000 LIPS）m_count（1，1）。％29推论，0.000 CPU在0.000秒内（31％CPU，1318182 LIPS）m_count（2，1）。％33推断，0.000 CPU在0.000秒内（76％CPU，1736842 LIPS）m_count（3，2）。％41推论，0.000秒内0.000 CPU（81％CPU，1952381 LIPS）m_count（4，4）。％61推论，0.000秒内0.000 CPU（88％CPU，2178571 LIPS）m_count（5，9）。％109推断，0.000 CPU在0.000秒内（91％CPU，2595238 LIPS）m_count（6，21）。％230推论，0.000秒内0.000 CPU（93％CPU，2948718 LIPS）m_count（7，51）。％538推论，0.000秒内0.000 CPU（97％CPU，3221557 LIPS）m_count（8，127）。％1,337推断，0.000 CPU在0.000秒内（99％CPU，3293103 LIPS）m_count（9，323）。％3,434推论，0.001秒的0.001 CPU（99％CPU，3400000 LIPS）m_count（10，835）。％9,000推论，0.003 CPU在0.003秒内（94％CPU，3301541 LIPS）m_count（11，2188）。％23,908推论，0.024秒的0.007 CPU（31％CPU，3300387 LIPS）m_count（12，5798）。％64,158推论，0.019 CPU 0.024秒（79％CPU，3387792 LIPS）m_count（13，15511）。％173,579推论，0.051 CPU在0.062秒内（83％CPU，3397448 LIPS）m_count（14，41835）。％472,853推论，0.139 CPU在0.152秒（92％CPU，3393690 LIPS）m_count（15，113634）。
prolog是一种很好的语言，用于生成根据声明性描述详尽地解决解决方案！
prolog recurrence the Recistrence the Recistrence，如@davideisenstat的建议：
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 ;
...
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中给出的复发转移了一个。