从F＃N叉树的叶提取路径 [英] Extracting Leaf paths from n-ary tree in F#

问题描述

灵感<一href="http://stackoverflow.com/questions/277106/looking-for-some-interesting-c-programming-problems">this问题，我想试试我的手，在最新的思考这个挑战，使用F＃

我的做法是可能完全偏离了航线，但在解决这个问题的过程中，我试图让数字的所有排列0-9。

名单

我在寻找解决它使用的是正叉树像这样：

 类型的节点=
    |分公司（INT *节点列表）
    | INT叶
 

我很高兴，我自己，因为我已经成功地解决如何产生，我想这棵树。

我现在的问题是，我可以不知道如何来遍历这棵树，并提取了路径，以每片叶子为int。事情的事就是困惑我的是，我需要匹配的单个节点，但我的'外'的功能需要采取一个节点列表。

我目前的尝试几乎做了正确的事情，只不过它返回我的所有路径的总和......

 让测试=分公司（3，[科（2，[叶（1）]）;科（1，[叶（2）]）]）

让REC游客LST ACC =
    让内N =
        匹配n，其中
        |叶（H） - ＆GT; ACC * 10 + H
        |分公司（H，T） - ＆GT;游客吨（ACC * 10 + H）
    List.map内LST |＆GT; List.sum

游客[测试] 0 //  - ＆GT;给出633（它是321 + 312）
 

和我什至不知道这是尾递归。

（你很欢迎提出了查找排列另一种解决方案，但我仍然有兴趣在解决这一特定问题）

编辑：我已经张贴在这里 F＃一个通用的排列算法。

解决方案

关于您的问题约列表遍历 - 您可以通过编写一个函数，返回重新present的路径列表，开始 - 这就是我想象的要容易，它会迟容易把它变成一个函数返回一个数字。

这其中将列表作为第一个参数（到目前为止路径），一棵树，并返回一个列表>类型 - 即从当前的分支中的所有可能的路径

。

 让REC游客LST树=
  匹配树
  |分公司（N，分） - ＆GT; List.map_concat（访问者（N :: LST））子
  |叶（N） - ＆GT; [List.rev（N :: LST）

// 例如...
＆GT;让TR =分公司（1，[叶（3）;科（2，[叶（4）;叶（5）]）]）;;
＆GT;游客[] TR ;;
VAL它：INT列表清单= [[1; 3]; [1; 2; 4〕; [1; 2; 5]
 

在'叶'的情况下，我们只需将当前号码到列表中，并返回结果为包含单独的列表（我们必须首先扭转这种局面，因为我们将号码开头）的列表。 在科的情况下，我们添加N到列表中，递归调用的游客来处理当前分支的所有子节点。这将返回一串名单，我们使用'map_concat'把它们变成一个列表，其中包含从当前分支中的所有posble路径。

现在，你可以重写这个返回一个整数列表：

 让REC visitor2 LST树=
  匹配树
  |分公司（N，分） - ＆GT; List.map_concat（visitor2（LST * 10 + N））子
  |叶（N） - ＆GT; [LST * 10 + N]

// 例如...
＆GT; visitor2 0 TR ;;
VAL它：INT表= [13; 124; 125]
 

不是将名单

，现在我们计算的数量。

T

Inspired by this question, I wanted to try my hand at the latest ponder this challenge, using F#

My approach is probably completely off course, but in the course of solving this problem, I'm trying to get a list of all the permutations of the digits 0-9.

I'm looking at solving it using a n-ary tree like so:

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

I'm quite pleased with myself, because I've managed to work out how to generate the tree that I want.

My problem now is that I can't work out how to traverse this tree and extract the 'path' to each leaf as an int. Thing thing that is confusing me is that I need to match on individual Nodes, but my 'outer' function needs to take a Node list.

My current attempt almost does the right thing, except that it returns me the sum of all the paths...

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)

And I'm not even sure that this is tail-recursive.

(You're quite welcome to propose another solution for finding permutations, but I'm still interested in the solution to this particular problem)

EDIT: I've posted a generic permutations algorithm in F# here.

解决方案

regarding your question about list traversal - you can start by writing a function that returns lists that represent the path - that's I think easier and it will be later easy to turn it into a function that returns a number.

This one takes a list as the first argument (path so far) and a tree and returns a list> type - that is all the possible paths from the current branch.

let rec visitor lst tree = 
  match tree with
  | Branch(n, sub) -> List.map_concat (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]]

In the 'Leaf' case, we simply add the current number to the list and return the result as a list containing single list (we have to reverse it first, because we were adding numbers to the beginning). In the 'Branch' case, we add 'n' to the list and recursively call the visitor to process all the sub-nodes of the current branch. This returns a bunch of lists and we use 'map_concat' to turn them into a single list that contains all posble paths from the current branch.

Now, you can rewrite this to return a list of integers:

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

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

Instead of concatenating lists, we now calculate the number.

T.

这篇关于从F＃N叉树的叶提取路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！