2

我想知道是否有人可以为以下问题提供更简化的解决方案或改进我的代码。

假设我们有一棵树，其分支的深度为“d”，我们想要修剪这棵树，这样我们在深度 d 处保留“ n”个分支，然后在深度d-1处保留另一个 n 个分支；然后在d-2等另一个n分支...

在我的解决方案中，我需要使用 adictionary来跟踪分支的数量和ref可变深度以跟踪和降低深度级别

很想知道一个更简单、更优雅的解决方案，或者任何提示/技巧来改进我所拥有的

数据结构

type MultiTree = | MNode of int * list<MultiTree>

测试树

let Mtree2 = MNode (0,
                    [MNode (1,[MNode (2,[MNode (3,[])])]);
                    MNode (1,[MNode (2,[MNode (3,[])])]);
                    MNode (1,[MNode (2,[MNode (3,[])])]);
                    MNode (1,[MNode (2,[MNode (3,[])])]);
                    MNode (1,[MNode (2,[MNode (3,[])])]);
                    MNode (1,[MNode (2,[MNode (3,[])])])])

修剪树功能

let trimTree noLosses depth t=
    let mlimit = ref depth
    let dict = Dictionary()

    let fn k =
        match dict.TryGetValue(k) with
        | true, l -> dict.[k] <- l + 1
        |_ -> dict.Add(k,1)
        if dict.[k] >= noLosses then mlimit := !mlimit - 1 else mlimit := !mlimit

    let rec loop d t  = 
        match t with
            | MNode(i,sub) when d > !mlimit ->  
                fn !mlimit      
                MNode(i, List.map (loop (d+1)) [])
            | MNode(i,sub) -> MNode(i, List.map (loop (d+1)) sub)
    loop 1  t


let Mtree2trimmed = Mtree2 |> trimTree 3 2

结果

使用 Thomas P 的“printTree”函数可以很好地可视化

let printt tree =
let rec loop depth (MNode(n, sub)) =
    printfn "%s %A" depth n
    for s in sub do loop (depth + "  ") s
loop "" tree

输出 -

printt Mtree2

 0
   1
     2
       3
   1
     2
       3
   1
     2
       3
   1
     2
       3
   1
     2
       3
   1
     2
       3

输出 -

printt Mtree2trimmed

 0
   1
     2
   1
     2
   1
     2
   1
   1
   1

所以，如果你已经做到了这一步 - 有什么建议吗？

干杯!

4

1 回答 1

1

这个问题称为。基本方法如下：

  1. 使用补充数据结构标记您的数据；
  2. 基于补充数据的处理；
  3. 减少以删除那些不应该出现在最终结果中的项目；此外，消除不再需要的补充数据。

让我们用补充值标记每个分支：

  • depth（0=最上面的分支）
  • sequential（对于每个子树，以 开头0）

为了实现这一点，我更改了树的定义，使其具有通用性：

type MultiTree<'T> = | MNode of 'T * list<MultiTree<'T>>

现在：

let rec mapper depth sequential = function
    | MNode(value, sub) ->
        MNode( (depth, sequential, value),
               (sub |> List.mapi (fun i value -> mapper (depth+1) i value))
             )

let tree1 = MNode (0,
                    [MNode (1,[MNode (2,[])]);
                    MNode (3,[]);])

printfn "Original data"
tree1 |> printt
printfn "Mapped data"
tree1 |> mapper 0 0 |> printt

结果将是：

Original data
 0
   1
     2
   3
Mapped data
 (0, 0, 0)
   (1, 0, 1)
     (2, 0, 2)
   (1, 1, 3)

现在，当数据被标记时，我们可以应用我们想要的任何过滤器。这里有三个例子，加上一个更大的树来展示所有的可能性：

// Take only first n branches at every level
let rec filter1 n = function
    // first subtrees pass (up to "noLosses" count)
    | MNode( (depth, sequential, value), sub)
        when sequential < n
                            -> Some(MNode(value, List.choose (filter1 n) sub))
    // the rest are skipped
    | _                     -> None

// Take "d" levels of branches unchanged, at higher levels take only second branch
let rec filter2 d = function
    | MNode( (depth, sequential, value), sub)
        when depth < d      // lower depth - pass

        || sequential = 1   // at higher levels, take only the second branch (=1)
                            -> Some(MNode(value, List.choose (filter2 d) sub))
    // the rest are skipped
    | _                     -> None

// Take only first n branches at every level;
// "n" is a list to identify maximal element at each level
let rec filter3 ns ts =
    match ns, ts with
    // Empty "noLosse" list -> no value
    | [], _                      -> None
    // if the sequential order of Tree branch is less than
    // the corresponding value in "ns" list, let the value pass the filter
    | nsHead :: nsTail, MNode((_, sequential, value), sub)
        when sequential < nsHead -> Some(MNode(value, List.choose (filter3 nsTail) sub))
    // the rest are skipped
    | _, _                       -> None

printfn "Original data"
tree2 |> printt
printfn "Filter1 applied"
tree2 |> mapper 0 0 |> filter1 2 |> Option.iter printt
printfn "Filter2 applied"
tree2 |> mapper 0 0 |> filter2 2 |> Option.iter printt
printfn "Filter3 applied"
tree2 |> mapper 0 0 |> filter3 [4; 4; 2] |> Option.iter printt

注意，我们需要，Option.iter因为过滤器可能会返回None值。

输出：

Original data
 1
   11
     111
       1111
       1112
       1113
   12
     121
       1211
     122
       1221
       1222
       1223
     123
     124
   13
     131
       1211
   14
     141
       1411
   15
     151
       1511
   16
     161
       1611
Filter1 applied
 1
   11
     111
       1111
       1112
   12
     121
       1211
     122
       1221
       1222
Filter2 applied
 1
   11
   12
     122
       1222
   13
   14
   15
   16
Filter3 applied
 1
   11
     111
   12
     121
     122
   13
     131
   14
     141

需要注意的是，这种方法并未针对性能进行优化。它的主要思想是展示如何将任务拆分为一系列较小的任务，以便实际过滤实际上是一个简单的匹配案例。

于 2013-08-15T03:44:19.323 回答