目前，我可以使用以下蛮力的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).
但是，这是效率低下的蛮力算法。
是否有一种更有效的算法来枚举有根的平面未标记二叉树？
注意：可以通过使用前两次迭代中的树，考虑斐波那契数并添加一元分支或二进制分支来生成树，但这会导致树重复。我自己可以做那个版本，我正在寻找的是一种算法，该算法可以在第一次没有重复的情况下高效地生成树。
注意：二进制树也称为二进制表达式树或K <= 2 的K元树。
我针对M（15）的蛮力版本花费了1小时27分钟，而针对M（15）的高效版本花费了大约2秒。
显然，高效算法就是这样，效率更高，而且我为什么要问这个问题。
具有N生根的平面未标记二叉树的节点的树数由Motzkin数给出。请参阅：OEIS A001006
N
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.
莫兹金数
<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在目录中创建了一个名为
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)
并检查莫兹金号
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))
完成此操作后，我得到了与OEIS搜索一起使用的数字1,2,4,9,21序列， 对于Motzkin数，最高结果为A001006。一旦有了更大的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中：
此递归枚举过程对应于递归
M_1 = 1 M_n = M_{n-1} + sum_{i=1}^{n-2} M_i M_{n-1-i},
与Wikipedia中给出的重复率相比偏移了一个。
