3

競馬の賭けのシナリオを使用して、レースの最初の 4 人のフィニッシャー (superfecta) を予測するために、いくつかの個別の賭けがあるとします。

賭け方は以下の通り…

1/2/3/4  
1/2/3/5  
1/2/4/3  
1/2/4/5  
1/2/5/3  
1/2/5/4

私がやりたいのは、これらの別々の組み合わせを可能な限り組み合わせたり、凝縮したりすることです。上記の賭けの場合、すべてを 1 行にまとめることができます...

1/2/3,4,5/3,4,5

しかし、リストから最後の賭けを削除すると、1/2/5/4 ...

1/2/3/4  
1/2/3/5  
1/2/4/3  
1/2/4/5  
1/2/5/3

圧縮された賭けは、代わりに 2 行にする必要があります。

1/2/3,4/3,4,5  
1/2/5/3

この場合、アルゴリズムはどのようになりますか?

4

2 に答える 2

2

こんなことをきれいな写真で考えるのが一番簡単だと思います。いくつかのグラフを作成してみませんか？

最初の例

1/2/3/4  
1/2/3/5  
1/2/4/3  
1/2/4/5  
1/2/5/3  
1/2/5/4

...グラフ形式で次のようになります。

前の例1

上から下への各パス（例1->2->4->3）は、初期形式の行に対応します。

そのグラフから始めると、（おそらく）グラフ上で小さなアルゴリズムを実行して、探している方法でグラフを単純化することができます。これが私たちが試みることです：

  • グラフの上部から開始し、レベルごとに下に移動します。（最初のレベルには青いノードのみが含まれます1。）
  • 現在のレベルのノードごとに、子の数を数えます。子が1つしかない場合は、ノードをスキップします。（青いノード1には子が1つしかないため、緑のノードにスキップします2。）
  • 複数の子のそれぞれについて、その子とその孫を含むセットを作成します。（赤いノード3にはセットがあり、{3,4,5}赤いノードにはセットがあり、赤いノードには4セットがあります。）{3,4,5}5{3,4,5}
  • これらのセットのいずれかが同一である場合は、関連付けられた子/孫を、セットを含む孫を指す、子を含む単一のノードに置き換えます。（3つの赤いノードはすべて同じセットであるため、すべて置き換えられます。）

後の例1

2番目の例

1/2/3/4  
1/2/3/5  
1/2/4/3  
1/2/4/5  
1/2/5/3

...グラフ形式で次のようになります。

前の例2

赤いノード3と4は同じセット（つまり{3,4,5}）を持っているので、それらは置き換えられます。赤いノードには赤いノードと5同じセットがないので、そのままにしておきます。34

後の例2

前と同じように、簡略化されたツリーを通る各パスは、出力の1行を表します。

（曾孫がいるときに子供/孫を入れ替えるとどうなるかについては説明していません。実際には一番下の列から始めて、上に向かって進んでいく必要があるかもしれません。）

于 2012-06-05T21:43:29.230 に答える
0

F＃による

open System
open System.Collections.Generic

let data =
  [|
    "1/2/3/4"
    "1/2/3/5"
    "1/2/4/3"
    "1/2/4/5"
    "1/2/5/3"
    "1/2/5/4"
  |]
let conv (xs:string []) =
  let xs = xs |> Array.map (fun x -> x.Split('/'))
  let len = xs.[0] |> Array.length
  let sa = Array.init len (fun _ -> new SortedSet<string>())
  xs |> Array.iter (fun xa -> xa |> Array.iteri (fun i x -> sa.[i].Add(x) |>ignore))
  String.Join("/", sa |> Array.map (fun x -> if Seq.length x = 1 then Seq.head x else String.Join(",", x |> Seq.toArray)))

let _ = 
  conv data |> printfn "%s"
//result:1/2/3,4,5/3,4,5

  //use 0-3 and 4 element of data
  [|data.[0..3]; data.[4..4] |]
  |> Array.map (fun x -> conv x)
  |> Array.iter (printfn "%s")
(* result:
1/2/3,4/3,4,5
1/2/5/3
*)
于 2012-06-05T10:37:26.507 に答える