相关疑难解决方法(0)

注意:我最后添加了很多Of interest评论.这些并不是在暗示一个人应该使用inline和static type parameters 威利愿意不愿意,他们有这么一个没有花时间搜索大量的SO与此相关的问题,以更好地理解这些概念的问题.

我知道当需要使函数通用并且需要零(0)值时,F#提供GenericZero.

解析为任何原始数字类型的零值或具有名为Zero的静态成员的任何类型.

所以这让我相信使用GenericZero字符串类型我只需要添加一个名为Zero的静态成员.

由于System.String是.Net框架的一部分,修改.Net源代码不是应该做的.但是,F#提供了Type Extensions.

类型扩展允许您将新成员添加到先前定义的对象类型.

此外,F#提供了String模块,但缺少GenericZero.

有关创建类型扩展的好教程,请参阅:将函数附加到类型.

我测试的代码:

这是在一个名为的项目中 Library1

namespace Extension.Test

module Extensions = 

    type System.String with
        static member Something = "a"

        static member StaticProp
            with get() = "b"

        static member Zero
            with get() = "c"

这是在一个名为的项目中 Workspace

namespace Extension.Test
module main =

    open Extensions

    [<EntryPoint>]
    let main argv = 

        let stringSomething = System.String.Something
        printfn …

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