标签: motzkin-numbers

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

然而,对于有向图,生成从Wilson算法得到的单向均匀生成树并不能确保图形是强连通的,并且似乎添加额外的边缘以使生成树双向会引入偏差您生成的图表.

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

我想生成所有的Motzkin编号并存储在一个数组中.公式如下:

我目前的实施速度太慢了:

void generate_slow() {
    mm[0] = 1;
    mm[1] = 1;
    mm[2] = 2;
    mm[3] = 4;
    mm[4] = 9;
    ull result;
    for (int i = 5; i <= MAX_NUMBERS; ++i) {
        result = mm[i - 1];
        for (int k = 0; k <= (i - 2); ++k) {
            result = (result + ((mm[k] * mm[i - 2 - k]) % MODULO)) % MODULO;
        }
        mm[i] = result;
    }
}

void generate_slightly_faster() {
    mm[0] = 1;
    mm[1] = …

目前,我可以使用以下暴力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数字的树的数量 …

我有一个代码,用于计算Motzkin数字:

module Main where

    -- Program execution begins here
    main :: IO ()
    main = interact (unlines . (map show) . map wave . (map read) . words)

    -- Compute Motzkin number
    wave :: Integer -> Integer
    wave 0 = 1
    wave 1 = 1
    wave n = ((3 * n - 3) * wave (n - 2) + (2 * n + 1) * wave (n - 1)) `div` (n + 2)

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

任何优化的想法？