2

次の問題について、より単純化された解決策やコードの改善を誰かが提供できるかどうか疑問に思っていました。

ある深さ"d"に向かう枝を持つ木があるとします。そして、深さ d の"n"枝と深さd -1の別の n 枝を保持するように、この木をトリミングしたいとします。次に、 d-2で別のn分岐など...

私の解決策dictionaryでは、枝の数を追跡し、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