Matching a list of tuples with tuple members

Question

Suppose I have a decimal*decimal list

 let tup = [(1M, 2M); (2M, 3M); (3M, 3M); (4M, 5M); (5M, 6M); (7M, 6M); (8M, 9M); (10M, 9M)] 

I need a function that can group all the values ​​together if they can be related, like

 map[(100, [1M; 2M; 3M]); (101, [4M; 5M; 6M; 7M]); (102, [8M; 9M; 10M])] 

I can't just do List.groupBy because it skips anything else that might be linked down the line with another decimal value. The int values ​​on the map are arbitrary. I would like to be able to “sow” the initial value, and then increase each correction by a certain value.

What does a function look like that can do this?

Answer 1

Is it right that by “connected” you mean that numbers represent nodes and tuples represent edges in an undirected graph? As far as I know, there is no function in the standard library that would do this. You can search for a library that performs basic graph operations. The operation you want to perform is splitting into related components .

You can also try to implement this function from scratch. Here is a somewhat nice try .

Answer 2

Here is one not-so-pretty solution:

 let tup = [(1M, 2M); (2M, 3M); (3M, 3M); (4M, 5M); (5M, 6M); (7M, 6M); (8M, 9M); (10M, 9M)] let findGroupings lst = let rec findGroup input previous acc = match input with | [] -> acc | (a,b)::t -> match previous with | [] -> if a >= b then findGroup t [] acc else findGroup t [b;a] acc | h::_ -> if a > h && a < b then findGroup t (b::(a::previous)) acc elif a > h && a >=b then let full = List.rev (a::previous) findGroup t [] (full::acc) elif a >= b then findGroup t [] ((List.rev previous)::acc) elif a < h then findGroup t [b;a] (previous::acc) else // a = h and a < b findGroup t (b::previous) acc findGroup lst [] [] |> List.rev 

Using

 let result = findGroupings tup 

gives

 val result : decimal list list = [[1M; 2M; 3M]; [4M; 5M; 6M; 7M]; [8M; 9M; 10M]] 

Answer 3

What you are trying to accomplish seems to have been adequately addressed; how to do this, here is one approach:

 let groupConnected initId idTups = let mergeGroups projectIds input = (List.empty<SortedSet<_>>, input) ||> List.fold (fun groups x -> let ids = projectIds x match groups |> List.tryFind (fun g -> g.Overlaps ids) with | Some g -> g.UnionWith ids groups | _ -> ids::groups) idTups |> mergeGroups (fun (a, b) -> SortedSet([| a; b |])) |> mergeGroups id |> List.sortBy (fun g -> g.Min) |> Seq.mapi (fun ig -> initId + i, List.ofSeq g) |> Map.ofSeq 

Testing with this and the following questions:

 > groupConnected 100 [(1M, 2M); (2M, 3M); (3M, 3M); (4M, 5M); (5M, 6M); (7M, 6M); (8M, 9M); (10M, 9M)];; val it : Map<int,decimal list> = map [(100, [1M; 2M; 3M]); (101, [4M; 5M; 6M; 7M]); (102, [8M; 9M; 10M])] > groupConnected 100 [(1M, 1M); (2M, 18M); (3M, 3M); (4M, 5M); (5M, 24M); (24M, 6M); (7M, 6M); (8M, 9M); (10M, 9M)];; val it : Map<int,decimal list> = map [(100, [1M]); (101, [2M; 18M]); (102, [3M]); (103, [4M; 5M; 6M; 7M; 24M]); (104, [8M; 9M; 10M])] 

Online demo