CODEWITHSUNDEEP
c#linqlistgrouping
StevieJ81
StevieJ81

Reputation: 745

LINQ (Or pseudocode) to group items by proximity

Is anybody able to enlighten me on how to use LINQ (or something more appropriate if necessary) to create a list of lists of integers that are grouped by the the proximity from each other.

Basically, I want to create groups where the numbers are within 5 of any other number.

So, given:

3 27 53 79 113 129 134 140 141 142 145 174 191 214 284 284

Produce the following list:

3 
27
53
79
113
129 134 
140 141 142 145
174
194
214
284 284

Thanks!

Upvotes: 5

Views: 869

Answers (3)

cordialgerm
cordialgerm

Reputation: 8503

class Program
{
    static void Main(string[] args)
    {
        foreach (IEnumerable<int> grp in nums.GroupsOfN(5))
            Console.WriteLine(String.Join(", ", grp));

        Console.ReadKey();
    }

    static List<int> nums = new List<int>()
    {
        3,
        27,
        53,
        79,
        113,
        129,
        134,
        140,
        141,
        142,
        145,
        174,
        191,
        214,
        284,
        284
    };


}

public static class Extensions
{
    public static IEnumerable<IEnumerable<int>> GroupsOfN(this IEnumerable<int> source, int n)
    {
        var sortedNums = source.OrderBy(s => s).ToList();

        List<int> items = new List<int>();
        for (int i = 0; i < sortedNums.Count; i++)
        {
            int thisNumber = sortedNums[i];
            items.Add(thisNumber);

            if (i + 1 >= sortedNums.Count)
            {
                yield return items;
            }
            else
            {
                int nextNumber = sortedNums[i + 1];

                if (nextNumber - thisNumber > n)
                {
                    yield return items.ToList();
                    items.Clear();
                }
            }
        }
    }
}

Upvotes: 2

dtb
dtb

Reputation: 217273

LINQ is not very good at things like rolling sums etc. A simple foreach loop is better here:

static IEnumerable<IEnumerable<int>> GroupByProximity(
    this IEnumerable<int> source, int threshold)
{
    var g = new List<int>();
    foreach (var x in source)
    {
        if ((g.Count != 0) && (x > g[0] + threshold))
        {
            yield return g;
            g = new List<int>();
        }
        g.Add(x);
    }
    yield return g;
}

Example:

var source = new int[]
{
    3, 27, 53, 79, 113, 129, 134, 140, 141, 142, 145, 174, 191, 214, 284, 284
};

foreach (var g in source.GroupByProximity(5))
{
    Console.WriteLine(string.Join(", ", g));
}

Output:

3
27
53
79
113
129, 134
140, 141, 142, 145
174
191
214
284, 284

Upvotes: 4

Eric J.
Eric J.

Reputation: 150108

Not sure about how to do it in Linq, but you can create a list of lists and populate the result in a single pass, so performance is O(n).

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ListCluster
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> input = new List<int>() { 3, 27, 53, 79, 113, 129, 134, 140, 141, 142, 145, 174, 191, 214, 284, 284 };
            input.Sort();

            List<List<int>> result = new List<List<int>>();

            int currentList = 0;
            int? previousValue = null;

            result.Add(new List<int>());

            foreach (int i in input)
            {
                if (!previousValue.HasValue || i - previousValue < 5)
                {
                    result[currentList].Add(i);
                }
                else
                {
                    currentList++;
                    result.Add(new List<int>());
                    result[currentList].Add(i);
                }

                previousValue = i;

            }

            foreach (List<int> list in result)
            {
                foreach (int r in list)
                {
                    Console.Write(r);
                    Console.Write(" ");
                }
                Console.WriteLine();
            }
        }
    }
}

Upvotes: 1

Related Questions