Скрытый список <int>к списку диапазонов - PullRequest
0 голосов
/ 29 августа 2018

Мне нужно преобразовать list целых чисел в список диапазонов.

У меня есть List<int>, который содержит 8, 22, 41. Этими значениями являются разрывы разделов в полном списке от 1 до 47.

Я пытаюсь получить список диапазонов, который содержит начальную и конечную строки. Выход должен быть

{(1,7),(8,21),(22,40),(41,47)}

Я пытался адаптировать решение из этого вопроса , но не могу заставить его работать.

Похоже, все должно быть просто, но, возможно, нет.

Ответы [ 4 ]

0 голосов
/ 30 августа 2018

Ответы, в которых указано, что вы должны изменять локальный код во время запроса, опасны, даже если программа работает; не впадайте в эту дурную привычку.

Самый простой способ решить эту проблему - написать блок итератора. Предположим, у вас есть очевидный тип Pair<T>; в C # 7 вы, вероятно, будете использовать кортеж; адаптировать его для использования кортежей - простое упражнение:

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

Это верный способ решить эту проблему. Если вы хотите стать немного глупым, вы можете использовать Zip. Начните с двух полезных методов расширения:

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

А теперь у нас есть:

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

Но это кажется ненужным барокко по сравнению с простой записью блока итератора напрямую. Кроме того, это повторяет коллекцию дважды, что, по мнению многих, является плохим стилем.

Милый способ решения проблемы - обобщить первое решение:

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

А теперь ваш метод:

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

Мне очень нравится этот последний. То есть нам дают 8, 22, 41, мы строим 1, 8, 22, 41, 48, а затем из этого мы отбираем пары и строим (1, 7), (8, 21), и т. Д.

0 голосов
/ 29 августа 2018

Попробуйте использовать Linq ; при условии, что диапазон имеет тип 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));

Итог:

(1, 7)
(8, 21)
(22, 40)
(41, 47)
0 голосов
/ 29 августа 2018

Это не очень чисто, но вы можете построить новый массив и цикл для заполнения пробелов. Это предполагает, что ваши числа отсортированы, и я использовал возврат Tuple<int, int>, потому что я не мог найти простые типы диапазонов, которые имели бы смысл. С этим кодом вам не нужно беспокоиться о сохранении состояния в переменной за пределами переменной цикла, и вам не нужно исключать какие-либо результаты.

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

или

GetRanges(1, 47, new [] { 8, 22, 41 }); 

Если вам нужно альтернативное решение pure-linq, вы можете использовать это,

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();
}
0 голосов
/ 29 августа 2018

Вы не указали целевой язык. Итак, в Scala один из способов сделать это:

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)

Какие отпечатки: List((1,7), (8,21), (22,40), (41,47))

В качестве альтернативы мы можем использовать рекурсию:

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)])
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...