Split list in sublists based on border values

Question

I would like to split an existing sorted list into multiple subscriptions based on entries from another list.

Say I have an array like this:

List<int> myList = [1,3,7,23,56,58,164,185]; 

and another list that determines in which places myList should be divided:

 List<int> borders = [4,59,170]; 

What is the shortest way to get a nested list where myList divided by the values ​​defined in borders , i.e. as follows:

 [[1,3],[7,23,56,58],[164],[185]] 

I already solved this by manually sorting through the lists, but I can imagine that it is simpler and shorter with Linq.

EDIT: There is one simplification: numbers cannot be the same with borders, so it is not possible for a number to be contained in myList and borders at the same time.

Answer 1

Since you want to group numbers into different groups, you will want to use GroupBy . The only difficulty is what you use as a key. To do this, you can use the largest border value, which is less than the number. This suggests that borders sorted though:

 List<int> myList = new List<int> { 1, 3, 7, 23, 56, 58, 164, 185 }; List<int> borders = new List<int> { 4, 59, 170 }; var groups = myList.GroupBy(i => borders.LastOrDefault(x => x < i)); foreach (var group in groups) { Console.WriteLine("{0}: {1}", group.Key, string.Join(", ", group)); } 

This gives the following result:

 0: 1, 3 4: 7, 23, 56, 58 59: 164 170: 185 

Note that this is not an entirely effective solution, as it will look for the corresponding myList key for each element in myList . If your list is sorted, as your example, then its more efficient loop for simultaneously matching myList numbers with the current or next border element. Thus, this solution is O(n * m) , while the solution O(n) possible. On the plus side, this allows myList be completely unsorted.

---

For those interested in O (n), it’s possible that this is one of the possible ways to group sequences:

 List<List<int>> groups = new List<List<int>>(); List<int> group = null; int k = -1; foreach (int num in myList) { if (k < 0 || num > borders[k]) { group = new List<int>(); groups.Add(group); k++; } group.Add(num); }