I need to convert a list of integers to a list of ranges.
I have a List<int> that contains 8, 22, 41. These values are the section breaks in a complete list from 1 to 47.
I am trying to get a list of ranges that contains a start line and end line. The output should be
{(1,7),(8,21),(22,40),(41,47)}
I have tried to adapt the solution from this question but can't get it to work.
Seems like it should be simple, but maybe not.
Answers which state that you should mutate a local during a query are dangerous even if the program works; do not get into this bad habit.
The easiest way to solve the problem is to write an iterator block. Let's suppose you have the obvious Pair<T> type; in C# 7 you would likely use a tuple; adapting this to use tuples is an easy exercise:
static IEnumerable<Pair<int>> MakeIntervals(
/* this */ IEnumerable<int> dividers, /* You might want an extension method.*/
int start,
int end)
{
// Precondition: dividers is not null, but may be empty.
// Precondition: dividers is sorted.
// If that's not true in your world, order it here.
// Precondition: dividers contains no value equal to or less than start.
// Precondition: dividers contains no value equal to or greater than end.
// If it is possible for these preconditions to be violated then
// the problem is underspecified; say what you want to happen in those cases.
int currentStart = start;
for (int divider in dividers)
{
yield return new Pair<int>(currentStart, divider - 1);
currentStart = divider;
}
yield return new Pair<int>(currentStart, end);
}
That's the right way to solve this problem. If you wanted to get a bit silly you could use Zip. Start with two helpful extension methods:
static IEnumerable<T> Prepend<T>(this IEnumerable<T> items, T first)
{
yield return first;
foreach(T item in items) yield return item;
}
static IEnumerable<T> Append<T>(this IEnumerable<T> items, T last)
{
foreach(T item in items) yield return item;
yield return last;
}
And now we have:
static IEnumerable<Pair<int>> MakeIntervals(
IEnumerable<int> dividers,
int start,
int end)
{
var starts = dividers.Prepend(start);
// This is the sequence 1, 8, 22, 41
var ends = dividers.Select(d => d - 1).Append(end);
// This is the sequence 7, 21, 40, 47
var results = starts.Zip(ends, (s, e) => new Pair<int>(s, e));
// Zip them up: (1, 7), (8, 21), (22, 40), (41, 47)
return results;
}
But this seems needlessly baroque compared to simply writing the iterator block directly. Also, this iterates the collection twice, which is considered by many to be bad style.
A cute way to solve the problem is to generalize the first solution:
static IEnumerable<R> SelectPairs<T, R>(
this IEnumerable<T> items,
IEnumerable<T, T, R> selector
)
{
bool first = true;
T previous = default(T);
foreach(T item in items) {
if (first) {
previous = item;
first = false;
}
else
{
yield return selector(previous, item);
previous = item;
}
}
}
And now your method is:
static IEnumerable<Pair<int>> MakeIntervals(
IEnumerable<int> dividers,
int start,
int end)
{
return dividers
.Prepend(start)
.Append(end + 1)
.SelectPairs((s, e) => new Pair<int>(s, e - 1);
}
I quite like that last one. That is, we are given 8, 22, 41, we construct 1, 8, 22, 41, 48, and then from that we pick off pairs and construct (1, 7), (8, 21), and so on.
It isn't very clean but you could build a new array and loop to fill in the blanks. This assumes your numbers are sorted coming in and I used a Tuple<int, int> return because I couldn't find any simple range types that made sense. With this code you dont have to worry about storing the state in a variable outside of the loop variable and you don't need to exclude any results.
public Tuple<int, int>[] GetRanges(int start, int end, params int[] input)
{
// Create new array that includes a slot for the start and end number
var combined = new int[input.Length + 2];
// Add input at the first index to allow start number
input.CopyTo(combined, 1);
combined[0] = start;
// Increment end to account for subtraction later
combined[combined.Length - 1] = end + 1;
// Create new array of length - 1 (think fence-post, |-|-|-|-|)
Tuple<int, int>[] ranges = new Tuple<int, int>[combined.Length - 1];
for (var i = 0; i < combined.Length - 1; i += 1) {
// Create a range of the number and the next number minus one
ranges[i] = new Tuple<int, int>(combined[i], combined[i+1] - 1);
}
return ranges;
}
Usage
GetRanges(1, 47, 8, 22, 41);
or
GetRanges(1, 47, new [] { 8, 22, 41 });
If you would like an alternative pure-linq solution you could use this,
public Tuple<int, int>[] GetRanges(int start, int end, params int[] input)
{
return input
.Concat(new [] { start, end + 1 }) // Add first and last numbers, adding one to end to include it in the range
.SelectMany(i => new [] { i, i - 1 }) // Generate "end" numbers for each start number
.OrderBy(i => i)
.Except(new [] {start - 1, end + 1}) // Exclude pre-first and post-last numbers
.Select((Value, Index) => new { Value, Index }) // Gather information to bucket values
.GroupBy(p => p.Index / 2) // Create value buckets
.Select(g => new Tuple<int, int>(g.First().Value, g.Last().Value)) // Convert each bucket into a Tuple
.ToArray();
}
Using C# ValueTuple and C# 8.0 Ranges and indices along with new switch expressions, the solution can be done in a bit nifty way by creating handy extension method:
/// <summary>
/// Integer List array extensions.
/// </summary>
public static class RangesExtension
{
/// <summary>
/// Creates list of ranges from single dimension ranges list.
/// </summary>
/// <param name="ranges">Single dimension ranges list.</param>
/// <param name="from">Range first item.</param>
/// <param name="to">Range last item.</param>
/// <returns>List of ranges.</returns>
public static List<(int, int)> ToListOfRanges(
this List<int> ranges,
int from,
int to)
{
var list = ranges.ToArray();
return list.OrderBy(item => item)
.Select((item, index) => GetNext(ranges, from, index))
.Append((list[^1], to))
.ToList();
}
/// <summary>
/// Returns next couple of ranges from initial array.
/// </summary>
/// <param name="ranges">Single dimension ranges list.</param>
/// <param name="from">Range first item.</param>
/// <param name="index">Range current item index.</param>
/// <returns>Value Tuple of ranges.</returns>
private static (int, int) GetNext(
List<int> ranges,
int from,
int index)
{
return index switch
{
0 => (from, ranges[index] - 1),
_ => (ranges[index - 1], ranges[index] - 1),
};
}
}
Try using Linq; assuming that range is of type Tuple<int, int>:
List<int> list = new List<int>() { 8, 22, 41};
int from = 1;
int upTo = 47;
var result = list
.OrderBy(item => item) // to be on the safe side in case of {22, 8, 41}
.Concat(new int[] { upTo + 1 }) // add upTo breaking point
.Select(item => new Tuple<int, int>(from, (from = item) - 1));
// .ToArray(); // in case you want to get materialized result (array)
Console.Write(String.Join(Environment.NewLine, result));
Outcome:
(1, 7)
(8, 21)
(22, 40)
(41, 47)
You didn't specify the target language. So, in Scala, one way of doing so is:
val breaks = List(8, 22, 41)
val range = (1, 47)
val ranges = (breaks :+ (range._2 + 1)).foldLeft((range._1, List.empty[(Int, Int)])){
case ((start, rangesAcc), break) => (break, rangesAcc :+ (start, break - 1))
}
println(ranges._2)
Which prints: List((1,7), (8,21), (22,40), (41,47))
Alternatively, we can use recursion:
def ranges(rangeStart: Int, rangeEnd: Int, breaks: List[Int]) = {
@tailrec
def ranges(start: Int, breaks: List[Int], rangesAcc: List[(Int, Int)]): List[(Int, Int)] = breaks match {
case break :: moreBreaks => ranges(break, moreBreaks, rangesAcc :+ (start, break - 1))
case nil => rangesAcc :+ (start, rangeEnd)
}
ranges(rangeStart, breaks, List.empty[(Int, Int)])
}