Find Closest Keys In KeyValuePair (C#)

Question

I'm trying to find the closest group of elements that qualify in sequence compared to an existing dictionary. The goal is to take first group of elements that contain string values in a specific order. In my case, I may have a larger list, that looks kinda like this:

{1, "ISO"}
{2, "AEA"}
...
{256, "OI"}
...
{302, "OI"}
{303, "N2"}
{304, "N2.5"}
...
{400, "N2"}

The objective of this is to find key value pairs that contain values in a specific order, and return the LOWEST key from those key value pairs. To get what I felt was halfway there, I extracted all of the possibilities of pairs that contain the values "OI," "N2," and "N2.5."

Suppose from this I have a Dictionary, which is built like this:

Dictionary map = new Dictionary<int,string>();

map.Add(new KeyValuePair<int, string>(256, "OI");
map.Add(new KeyValuePair<int, string>(302, "OI");
map.Add(new KeyValuePair<int, string>(303, "N2");
map.Add(new KeyValuePair<int, string>(304, "N2.5");
map.Add(new KeyValuePair<int, string>(400, "N2");

I'd like to pull out the elements from this Dictionary whose key is closest to the other, so that I get a list in ascending order, like the KeyValuePairs containing 302, 303, and 304 as the keys. What's the best way to go about this?

You do not have enough info. It is very unclear what you are asking for. Do you plan on supplying a number and get number close to it by max 1,2,3..etc ? Are you looking to group by sequential values ? — Franck, Jul 04 '19 at 17:44
@Franck I simply want to return the key value pairs whose keys are closest to each other so that I can return the lowest key of THAT group. For example, I want to return the key from the key value pair containing 302 as the key, since that is closest in key sequence with the other two. It's part of a larger project I'm doing with collecting matches from regular expressions. — Kieran Ojakangas, Jul 04 '19 at 17:47
@steve16351 I see what you mean. Let me revise the question. — Kieran Ojakangas, Jul 04 '19 at 17:57
You could do it with a lamda expression. Iterate two times through your map, and use Select and create a new type which contains the difference between two items and add both items to this type. Afterwards you just have to order the new list by the difference and take the first item. — Mitja, Jul 04 '19 at 18:11
@Mitja I figured I could. Can you show what that would look like maybe? — Kieran Ojakangas, Jul 04 '19 at 18:12
Sorry, I'm on my mobile phone. But the instructions I added to my first comment should help. — Mitja, Jul 04 '19 at 18:15
So short story, you want to find the smallest gap between all the keys. Then you want to get all keys that have the gap you just found and group by consecutive sequence. — Franck, Jul 04 '19 at 18:22
@Franck, yeah I think that's right. To add to that, the keys should ONLY be separated by 1. So I can't have keys that are off even by a value of 2. — Kieran Ojakangas, Jul 04 '19 at 18:23
@KieranOjakangas that is a very important point. That makes things much easier with a single loop — Franck, Jul 04 '19 at 18:25
@KieranOjakangas are you planning to [edit] your post to clearly specify that you are looking for splitting into groups of sequential numbers? Otherwise looks like duplicate of https://stackoverflow.com/questions/20230475/which-clustering-algorithm-is-suitable-for-one-dimensional-lists-without-knowing — Alexei Levenkov, Jul 04 '19 at 20:08

Mitja · Answer 1 · 2019-07-04T19:08:00.707

And there we go:

    Dictionary<int, string> map = new Dictionary<int, string>();

    map.Add(256, "OI");
    map.Add(302, "OI");
    map.Add(303, "N2");
    map.Add(304, "N2.5");
    map.Add(400, "N2");
    var minDiffGroup = map.SelectMany(item1 =>
         map
         .Where(item2 => !object.Equals(item1, item2))
         .Select(item2 => new { Diff = Math.Abs(item1.Key - item2.Key), Item1 = item1, Item2 = item2 })
      )
      .GroupBy(item => item.Diff)
      .OrderBy(group => group.Key)
      .FirstOrDefault();

    Console.WriteLine("Diff: {0}", minDiffGroup.Key);
    foreach (var item in minDiffGroup)
        Console.WriteLine("Item 1: {0}\tItem 2:{1}", item.Item1, item.Item2);
    Console.ReadKey();

Output:

Diff: 1
Item 1: [302, OI]       Item 2:[303, N2]
Item 1: [303, N2]       Item 2:[302, OI]
Item 1: [303, N2]       Item 2:[304, N2.5]
Item 1: [304, N2.5]     Item 2:[303, N2]

I would help further, but your question is very vague.

Edit

Okay, after you added some more information, I changed my lamda expression:

    Dictionary<int, string> map = new Dictionary<int, string>();

    map.Add(256, "OI");
    map.Add(302, "OI");
    map.Add(303, "N2");
    map.Add(304, "N2.5");
    map.Add(400, "N2");
    var orderedMap = map.OrderBy(item => item.Key); // Order the map
    var minDiffGroup = orderedMap.SelectMany(item1 =>
         orderedMap
         .SkipWhile(item2 => !object.Equals(item1, item2)) //skip all elements which were already merged
         .Skip(1) //skip item1 == item2
         .Select(item2 => new { Diff = Math.Abs(item1.Key - item2.Key), Item1 = item1, Item2 = item2 }) //create an unknown type with Key = diff and both items
      )
      .GroupBy(item => item.Diff) //group by Diff
      .OrderBy(group => group.Key) //order by Diff
      .FirstOrDefault(); //Take the smallest group

    if (minDiffGroup?.Count() > 0)
    {
        var lowestChain = minDiffGroup
             .OrderBy(item => item.Item1.Key) //order by the key of item1
             .TakeWhile(item => item.Item1.Key + minDiffGroup.Key == item.Item2.Key) //take all items as long as the next item has the difference of this group (otherwise there is a gap)
             .SelectMany(item => new List<KeyValuePair<int, string>>() { item.Item1, item.Item2 }) //select all collected KeyValuePairs
             .Distinct(); //take every once
        foreach (var item in lowestChain)
        {
            Console.WriteLine(item);
        }
    }

Output:

[302, OI]
[303, N2]
[304, N2.5]

score 1 · Answer 2 · answered Jul 04 '19 at 18:58

Here a basic quick version with detail explanation if you want to learn from it at the same time.

The overall logic is pick the first item, keep iterating until it's not a sequence anymore. Then check if you just iterated at least 2 consecutive number if yeas great keep it and retry with next available number until all numbers have been iterated over.

Dictionary<int, string> map = new Dictionary<int, string>();

map.Add(256, "OI");
map.Add(302, "OI");
map.Add(303, "N2");
map.Add(304, "N2.5");
map.Add(400, "N2");

// will contain the final results.
Dictionary<int, string> results = new Dictionary<int, string>();

// get map ordered
var mapList = map.OrderBy(o => o.Key).ToList();

// iterate until we have worked out each values
while (mapList.Any())
{
    // take first item
    var item = mapList[0];

    // kepp the index of found consecutive values                             
    var index = 0;

    // loop for each value
    for (int i = 1; i < mapList.Count; i++)
    {
        // if the value isn't 1 higher get out the loop
        if (mapList[i].Key != mapList[index].Key + 1)
        {
            break;
        }
        else
        {
            // value is more than 1 so keep going until we can't
            index++;
        }
    }

    // if we have found at least 2 consecutive numbers
    if (index > 0)
    {
        // add the first of the sequence
        results.Add(item.Key, item.Value);

        // add the rest of the sequence that was found
        for (int i = 0; i < index; i++)
        {
            results.Add(mapList[i + 1].Key, mapList[i + 1].Value);
        }

        // finally removed all items found plus the starting item (hence the + 1)
        mapList.RemoveRange(0, index + 1);
    }
    else
    {
        // no consecutive numbers found so just remove the item so we can loop and try the next one
        mapList.RemoveAt(0);
    }
}

I like this answer. I actually ended doing something just like that but with slightly different functions. — Kieran Ojakangas, Jul 04 '19 at 19:00

Find Closest Keys In KeyValuePair (C#)

2 Answers2