LINQ (or pseudo-code) for grouping elements by proximity

Question

Can someone 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 proximity to each other.

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

So, considering:

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

Create the following list:

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

Thanks!

Answer 1

LINQ is not very good at things like current amounts, etc. A simple foreach 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

Answer 2

 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(); } } } } } 

Answer 3

Not sure how to do this in Linq, but you can create a list of lists and populate the result in one pass, so the 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(); } } } }