6

受这个问题的启发，我最近想尝试一下这个挑战，使用 F#

我的方法可能完全偏离了方向，但在解决这个问题的过程中，我试图获取数字 0-9 的所有排列的列表。

我正在考虑使用像这样的 n-ary 树来解决它：

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

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

我现在的问题是我无法弄清楚如何遍历这棵树并将每个叶子的“路径”提取为一个 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# 中的通用排列算法。

4

2 回答 2

5

关于您关于列表遍历的问题-您可以从编写一个返回表示路径的列表的函数开始-我认为这更容易，以后将其转换为返回数字的函数会很容易。

这个将一个列表作为第一个参数（到目前为止的路径）和一个树并返回一个 list> 类型 - 这是来自当前分支的所有可能路径。

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]]

在“叶子”的情况下，我们只需将当前数字添加到列表中并将结果作为包含单个列表的列表返回（我们必须先将其反转，因为我们在开头添加了数字）。在“分支”的情况下，我们将“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]

我们现在计算数量，而不是连接列表。

于 2008-11-12T11:12:48.273 回答
2

关于懒惰 - 你可以通过使用 F#“seq”类型而不是“list”类型来使这个懒惰。这是一个例子：

let rec visitor2 lst tree =
  match tree with
  | Branch(n, sub) -> Seq.map_concat (visitor2 (lst * 10 + n)) sub
  | Leaf(n) ->
      seq { do printfn "--yielding: %d" (lst * 10 + n)
            yield lst * 10 + n };;

“seq” 是一个序列表达式，它表示一个惰性值流。我在代码中添加了“printfn”，这样我们就可以跟踪事情的执行情况：

> visitor2 0 tr |> Seq.take 2;;
--yielding: 13
--yielding: 124
val it : seq<int> = seq [13; 124]

您可能可以使用 Seq.first 之类的东西来查找代表结果的第一个值。

于 2008-11-12T12:04:38.387 回答