从F#中的n-ary树中提取叶子路径

受到这个问题的启发,我想尝试用最新的思考这个挑战,使用F#

我的方法可能完全偏离正轨,但在解决这个问题的过程中,我试图得到一个数字0-9的所有排列的列表.

我正在寻找使用像这样的n-ary树来解决它:

type Node = 
    | Branch of (int * Node list)
    | Leaf of int

我对自己很满意,因为我已经设法弄清楚如何生成我想要的树.

我现在的问题是我无法弄清楚如何遍历这个树并将每个叶子的'path'作为int提取出来.令我困惑的事情是我需要匹配单个节点,但我的"外部"功能需要采用节点列表.

我当前的尝试几乎做了正确的事情,除了它返回我所有路径的总和......

let test = Branch(3, [Branch(2, [Leaf(1)]);Branch(1, [Leaf(2)])])

let rec visitor lst acc = 
    let inner n = 
        match n with
        | Leaf(h) -> acc * 10 + h
        | Branch(h, t) -> visitor t (acc * 10 + h)
    List.map inner lst |> List.sum

visitor [test] 0 //-> gives 633 (which is 321 + 312)

我甚至不确定这是尾递归.

(非常欢迎您提出另一种寻找排列的解决方案,但我仍然对这个特定问题的解决方案感兴趣)

编辑:我已经张贴在F#泛型算法排列在这里.

关于列表遍历的问题 - 你可以从编写一个返回表示路径的列表的函数开始 - 我觉得这很容易,以后会很容易将它变成一个返回数字的函数.

这个列表作为第一个参数(到目前为止的路径)和一个树并返回一个列表>类型 - 这是当前分支的所有可能路径.

let rec visitor lst tree = 
  match tree with
  | Branch(n, sub) -> List.collect (visitor (n::lst)) sub
  | Leaf(n) -> [List.rev (n::lst)]

// For example...
> let tr = Branch(1, [Leaf(3); Branch(2, [Leaf(4); Leaf(5)] )]);;
> visitor [] tr;;
val it : int list list = [[1; 3]; [1; 2; 4]; [1; 2; 5]]

在'Leaf'的情况下,我们只需将当前数字添加到列表中,并将结果作为包含单个列表的列表返回(我们必须先将其反转,因为我们在开头添加数字).在'Branch'的情况下,我们在列表中添加'n'并递归调用访问者来处理当前分支的所有子节点.这将返回一堆列表,我们使用'map_concat'将它们转换为包含当前分支中所有可用路径的单个列表.

现在,您可以重写它以返回整数列表:

let rec visitor2 lst tree = 
  match tree with
  | Branch(n, sub) -> List.collect (visitor2 (lst * 10 + n)) sub
  | Leaf(n) -> [lst * 10 + n]

// For example...  
> visitor2 0 tr;;
val it : int list = [13; 124; 125]  

我们现在计算数字,而不是连接列表.