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只有一个孩子，我们将跳到绿色节点2。）
  • 对于多个孩子中的每一个，构造一个包含该孩子及其孙子的集合。（红色节点3有一个集合{3,4,5}，红色4有一个集合{3,4,5}，红色5有一个集合{3,4,5}。）
  • 如果这些集合中的任何一个相同，则将关联的孩子/孙子替换为包含孩子的单个节点，指向包含集合的孙子。（因为所有三个红色节点都有相同的集合，所以它们都被替换了。）

示例 1 之后

第二个例子

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 之后

和以前一样，通过简化树的每条路径代表输出的一行。

（我没有介绍如果在有曾孙时替换子/孙会发生什么。可能是您实际上应该从底行开始并向上工作。）

于 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 回答