CODEWITHSUNDEEP
algorithmcombinations
Eddie Kuse
Eddie Kuse

Reputation: 51

Algorithm for condensing/consolidating number combinations

Using a horse race betting scenario, say I have a number of separate bets for predicting the first 4 finishers of the race (superfecta).

The bets are as follows...

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

What I want to do is combine or condense these separate combinations as much as possible. For the bets above, they can be all condensed into 1 line...

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

But if I removed the last bet from the list: 1/2/5/4 ...

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

The condensed bets would instead have to now be 2 lines:

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

What would algorithm look like for this?

Upvotes: 3

Views: 392

Answers (2)

Nate Kohl
Nate Kohl

Reputation: 35914

I find it easiest to think about this kind of thing with pretty pictures. How about we try to build some graphs?

First example

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

...could look like this, in graph form:

example 1 before

Each path from top to bottom (e.g. 1->2->4->3) corresponds to a row in your initial format.

If we start with that graph, then (perhaps) we can run a little algorithm on the graph that will simplify it in the way you're looking for. Here's what we'll try:

  • Start at the top of the graph, and move down level by level. (The first level contains only the blue node 1.)
  • For each node in the current level, count the number of children. If there is only one child, skip the node. (Since blue node 1 only has one child, we'll skip to green node 2.)
  • For each of the multiple children, construct a set that contains that child and its grandchildren. (The red node 3 has a set {3,4,5}, red 4 has a set {3,4,5}, and red 5 has a set {3,4,5}.)
  • If any of these sets are identical, replace the associated children/grandchildren with a single node containing the children, pointing to a grandchild that contains the set. (Since all three red nodes have identical sets, they all get replaced.)

example 1 after

Second example

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

...could look like this, in graph form:

example 2 before

The red nodes 3 and 4 have identical sets (i.e. {3,4,5}), so they get replaced. Red node 5 doesn't have the same set as red nodes 3 and 4, so we leave it alone.

example 2 after

As before, each path through the simplified tree represents one row of your output.

(I haven't covered what happens if you replace children/grandchildren when there are great-grandchildren. It could be that you should actually start at the bottom row and work your way upwards.)

Upvotes: 2

BLUEPIXY
BLUEPIXY

Reputation: 40145

by 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
*)

Upvotes: 0

Related Questions