问题标签 [motzkin-numbers]

我想生成所有Motzkin 数并存储在一个数组中。公式如下：

我目前的实现太慢了：

此外，我坚持为递归矩阵找到一个封闭形式，以便我可以应用幂平方。任何人都可以提出更好的算法吗？谢谢。
编辑我不能应用第二个公式，因为对数字取模时除法不适用。的最大值n为 10,000，超出了 64 位整数的范围，因此答案是模数较大m，其中m= 10^14 + 7。不允许使用更大的整数库。

所以我一直在构建一个程序，它使用蒙特卡罗模拟来寻找进化图论的属性。其关键功能之一是能够生成均匀分布的随机图，以便我们可以确定图的广义属性。对于连接的无向图，我已经实现了这个答案中概述的解决方案。

然而，对于有向图，生成从 Wilson 算法获得的单向统一生成树并不能确保图是强连接的，并且似乎添加额外的边以使生成树双向会引入偏差您生成的图表。

我觉得我可能遗漏了一些明显/误解的东西，但基本上我的要求是，有人可以向我推荐一个高级方案，允许我生成强连接、均匀分布、随机有向图吗？

我有一个计算 Motzkin 数的代码：

但是即使是一个简单的数字的输出也30需要一段时间才能返回。

有什么优化思路吗？？

目前，我可以使用以下蛮力 Prolog 代码枚举有根 平面 未标记二叉树。

注意：请参阅下面的输出列表。

并使用增加的大小输出它们

然而，这是低效的蛮力算法。

是否有更有效的算法来枚举有根平面未标记二叉树？

注意：可以通过使用前两次迭代中的树来生成树，想想斐波那契数，并添加一元分支或二元分支，但这会导致重复树。我自己可以做那个版本，我正在寻找的是一种算法，它第一次以有效的方式生成树而没有重复。

注意：二叉树也称为二叉表达式树或 K <=2 的K-ary 树。

补充

结果

我的 M(15) 的蛮力版本需要 1 小时 27 分钟，而 M(15) 的高效版本大约需要 2 秒。

显然，有效的算法就是这样，效率更高，也是我问这个问题的原因。

莫茨金数

具有根平面未标记二叉树节点的树的数量N由 Motzkin 数给出。参见：OEIS A001006

对于有根平面未标记二叉树，具有 N 个内部节点的树的数量由加泰罗尼亚数给出。有一种更有效的算法可以使用加泰罗尼亚数生成有根平面二叉树。

注意：
基于加泰罗尼亚数字的树数没有一元分支，只计算内部节点。

尽管

基于 Motzkin 数的树数确实具有一元分支并计算所有节点。

请参阅：汤姆戴维斯的
OEIS A000108
加泰罗尼亚语数字

将 Prolog 列表元素与 Motzkin 数相关联

使用低效的蛮力版本的统计信息

参考

Philippe Flajolet 和 Robert Sedgewick 所著的“Analytic Combinatorics”是一本可能有帮助的可免费下载的 pdf 书

另请参阅加泰罗尼亚语标签中的参考资料。

莫茨金数

BNF

使用David Eisenstat 的回答

对我来说，将这些视为笔记或面包屑，以防在我忘记它的几个月后需要再次使用它。

为了测试答案，我使用了安装了 Python 3 的WSL（适用于 Linux 的 Windows 子系统）

motzkin.py使用 Windows 10 我在目录中创建了一个名为

使用 Python 代码

然后在 WSL 中，我创建了一个指向 Windows Prolog 目录的符号链接

并更改为 WSL Prolog 目录

然后开始 Python3

并导入 Python 代码

并以 ubtrees 为 Motzkin 数的参数运行以下命令

并检查 Motzkin 数

退出交互式 Python 使用

重复注释

我了解 Motzkin 数的方法是用笔和纸手动枚举树，并通过使用将一元分支添加到前面的树 M(N-1) 和二进制分支到前面的 M(N -2）树木。

这棵树从 M(4) 棵树中为 M(5) 生成了两次

第一个通过添加一元分支到

其次通过添加一元分支到

完成此操作后，我得到了用于 OEIS 搜索的数字序列 1、2、4、9、21，最上面的结果是Motzkin 数字的A001006。一旦我有了更大的 Motzkin 数字列表，我就使用 Prolog 代码为更大的输入值生成计数，他们都同意了。现在，您可以将 OEIS 添加到您的编程工具箱中，并通过一个有效的示例向其他人演示。

更大的图景

如果你已经读到这里，那么你可能会看到这是一个更大的问题的一部分，它首先在 Prolog 中构建一个系统，可以使用术语重写来解决数学表达式直到基本微积分，但更重要的是显示所采取的步骤。因此，这为生成用作测试用例的二元表达式树提供了一部分方法。下一步是能够单独设置一元和二元节点的数量，而不是让它们由 Motzkin 数固定。我只使用 Motzkin 数字来验证我是否正确生成了组合的子集。现在我有了模式，我可以修改它以接受一个参数用于一元节点的数量，一个用于二进制节点。请参阅：如何使用具有 CLP(FD) 和多个约束的 DCG 枚举组合

只有当我遇到困难时，我才会提出与此相关的问题，所以不要指望看到所有必要的面包屑。

序言输出

我正在使用动态编程（在 R 中）来填充数组中的大约 20,000 个单元。我需要最后一个单元格中的确切整数。该函数只需要加法、乘法和逻辑表达式。

如果我用双精度数运行我的函数，它会在大约 30 秒内完成计算，但确切的整数大约是 50 位长，当然双精度数不能完全表示它。

当我尝试使用 mpfr 数字或大整数 ('bigz') 时，该函数的运行速度至少慢了一个数量级。有没有一种方法可以同时获得大量、高精度和速度？

（对于上下文，我正在尝试计算 Motzkin 数，以找出给定 RNA 序列有多少可能的稳定结构。这是使用 mpfr 数的代码。“s​​”是一个长度约为 200 个字符的字符串。）

我有以下输出 motzkin 数字的代码，我想将 yield 表达式更改为另一个更简单的表达式或函数，我该怎么做，我该怎么办？谢谢