Mapping a list of tuples by tuple members

Question

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?

As is, the question is pretty unclear. What is your definition of "connected"? Is Bartek's assumption correct that you want to find connected components of a graph? If that's the case, why are you working with decimals rather than integers? — Anton Schwaighofer, Sep 09 '16 at 08:30
In reality, they're `(billingID, shippingID)` and the exercise is trying to group customers together. I wouldn't have thought of this as a graph problem, but then again, I'm new to graph theory. — Steven, Sep 09 '16 at 13:07
In a given pair `(x, y)`, can `x` and `y` ever differ by more than `1M`? (They don't in your example data, but that could be happenstance.) — ildjarn, Sep 09 '16 at 19:31
Yes, that's just happenstance of my example. I'm looking at the [QuickGraph library](http://quickgraph.codeplex.com/documentation) now in the hopes that I can find something suitable. — Steven, Sep 09 '16 at 19:50

score 3 · Accepted Answer · answered Sep 08 '16 at 17:32

3

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.

answered Sep 08 '16 at 17:32

Bartek Kobyłecki

2,365
14
24

This answer led me to the [`QuickGraph` library](https://quickgraph.codeplex.com/). – Steven Sep 24 '16 at 17:34

ildjarn · Answer 2 · 2016-09-15T15:30:04.917

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

score 1 · Answer 3 · answered Sep 08 '16 at 20:58

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]]

This fails with differently-sorted input, e.g. `[(1M, 2M); (3M, 3M); (4M, 5M); (7M, 6M); (8M, 9M); (10M, 9M); (5M, 6M); (2M, 3M)]`. ([Demo](https://ideone.com/NDLHr2)) — ildjarn, Sep 15 '16 at 10:39

Mapping a list of tuples by tuple members

3 Answers3

Linked