CODEWITHSUNDEEP
f#
Steven
Steven

Reputation: 3292

Mapping a list of tuples by tuple members

Suppose I have a list of decimal*decimal

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 of the values together if they can be connected, e.g., 

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

I can't just do a List.groupBy because that misses anything else that may be connected "down the line" by another decimal value. The int values in the map are arbitrary. I'd like to be able to "seed" the starting value then increase each incrementally by some value.

What's the function look like that can do this?

Upvotes: 2

Views: 399

Answers (3)

ildjarn
ildjarn

Reputation: 62975

What you're trying to accomplish seems to be adequately addressed already; as to how to accomplish it, here's 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 i g -> initId + i, List.ofSeq g)
    |> Map.ofSeq

Testing with this and your followup question's inputs:

> 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

Upvotes: 2

Ringil
Ringil

Reputation: 6537

Here is one not very 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]]

Upvotes: 1

Bartek Kobyłecki
Bartek Kobyłecki

Reputation: 2395

Am I right that by 'connected' you mean that numbers represent nodes and tuples represent edges in undirected graph? As far as I know there is no function in standard library which would do that. You can search for some library that perform basic graph operations. The operation you want to perform is division to connected components.

You can also try to implement that function from the scratch. Here is some nice attempt.

Upvotes: 3

Related Questions