6

この質問に触発されて、F# を使用して、この課題について最新の熟考に取り組みたいと思いました。

私のアプローチはおそらく完全にコースから外れていますが、この問題を解決する過程で、数字 0 から 9 のすべての順列のリストを取得しようとしています。

次のようなn分木を使用して解決することを検討しています：

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

「Leaf」の場合、現在の番号をリストに追加し、単一のリストを含むリストとして結果を返します (最初に番号を追加していたため、最初に逆にする必要があります)。「ブランチ」の場合、リストに「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

怠惰について - 「list」型の代わりに F# の「seq」型を使用すると、これを怠惰にすることができます。次に例を示します。

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 に答える