Как бы вы отобразили массив целых чисел в виде набора диапазонов? (алгоритм)

Question

Учитывая массив целых чисел, как проще всего перебрать его и выяснить все диапазоны, которые он охватывает? например, для массива, такого как:

$numbers = array(1,3,4,5,6,8,11,12,14,15,16);

Диапазоны будут:

 1,3-6,8,11-12,14-16

Answer 1

Если массив отсортирован в порядке возрастания, проблема проста. Определите Range структуру или класс, который имеет начало и конец. Затем пройдитесь по массиву. Если текущий элемент больше предыдущего, обновите Range.end, в противном случае создайте новый диапазон с этим элементом как Range.begin. Сохраните диапазоны в динамический массив или связанный список. Или просто распечатайте их на ходу.

Если массив не может быть отсортирован, то сначала отсортируйте его.

Answer 2

Вот способ C # 3.0'y:

Достопримечательности:

• автоматические свойства (public int Property {get; set;})
• с использованием новых инициализаторов объектов (new Range {Begin = xxx; ...}
• с использованием доходности для ленивых вычислений
• с использованием методов расширения linq (First () и Skip ())

-

class Demo
{
    private class Range
    {
        public int Begin { get; set; }
        public int End { get; set; }

        public override string ToString()
        {
            if (Begin == End)
                return string.Format("{0}", Begin);
            else
                return string.Format("{0}-{1}", Begin, End);
        }
    }

    static void Main(string[] args)
    {
        var list = new List<int> { 1, 3, 4, 5, 6, 8, 11, 12, 14, 15, 16 };
        // list.Sort();
        var ranges = GetRangesForSortedList(list);

        PrintRange(ranges);

        Console.Read();
    }

    private static void PrintRange(IEnumerable<Range> ranges)
    {
        if (ranges.Count() == 0)
            return;

        Console.Write("[{0}", ranges.First());

        foreach (Range range in ranges.Skip(1))
        {
            Console.Write(", {0}", range);
        }

        Console.WriteLine("]");
    }

    private static IEnumerable<Range> GetRangesForSortedList(IList<int> sortedList)
    {
        if (sortedList.Count < 1) 
            yield break;

        int firstItem = sortedList.First();
        Range currentRange = new Range { Begin = firstItem, End = firstItem };

        foreach (int item in sortedList.Skip(1))
        {
            if (item == currentRange.End + 1)
            {
                currentRange.End = item;
            }
            else
            {
                yield return currentRange;
                currentRange = new Range { Begin = item, End = item };
            }
        }

        yield return currentRange;
    }
}

Приветствия, Дэвид

Answer 3

Если массив отсортирован, как в вашем примере, я бы определил сегменты, содержащие мин и макс.

Инициализация: создание корзины с минимальным и максимальным значениями, равными первому значению.

Loop: Сравните каждое значение с максимальным значением текущего сегмента. Если оно равно или на 1 больше текущего максимума, обновите макс. Если оно больше, чем на 1, больше максимума, сохраните корзину в список групп и запустите новую группу.

В конце у вас будет набор ведер с минимумом и максимумом в каждом. Если min совпадает с max, выведите одно число (т.е. в вашем примере первое ведро будет иметь min и max 1). Если они разные, выведите в качестве диапазона.

Пример реализации в lisp:

CL-USER> (defun print-ranges (integer-list)
           (let ((sorted-list (sort integer-list #'<)))
             (loop with buckets = ()
                   with current-bucket
                   for int in sorted-list
                     initially (setf current-bucket (cons (first sorted-list) (first sorted-list)))
                   do (cond ((= int (cdr current-bucket))) ; do nothing, this number is already in range
                            ((= (1- int) (cdr current-bucket)) ; number is 1 higher--update bucket's max
                             (setf (cdr current-bucket) int))
                            (t
                             (push current-bucket buckets)
                             (setf current-bucket (cons int int)))) ; set up a new bucket
                   finally (push current-bucket buckets)
                           (loop for firstp = t then nil
                                 for bucket in (nreverse buckets) do
                                   (cond ((= (car bucket) (cdr bucket))
                                          (format t "~:[,~;~]~D" firstp (car bucket)))
                                         (t
                                          (format t "~:[,~;~]~D-~D" firstp (car bucket) (cdr bucket))))))))
PRINT-RANGES
CL-USER> (print-ranges (list 1 3 4 5 6 8 11 12 14 15 16))
1,3-6,8,11-12,14-16
NIL
CL-USER> 

По сути, вы получаете список вещей, в которых есть каждая вещь (самая низкая в корзине, самая высокая в корзине). Это ваши диапазоны.

Если список еще не отсортирован, сначала отсортируйте его.

Answer 4

первый: сортировка второе: жетон затем: выведите первое значение и зациклите последующие. Если текущее значение равно последнему значению +1, пропустите его. В противном случае, если вы пропустили значение, напечатайте тире и значение, иначе выведите запятую и повторите.

Это должно сделать. Разве вы не хотели, чтобы я написал для вас домашнюю работу? :)

Answer 5

Вот реализация Python, она должна быть достаточно простой, чтобы следовать

numbers = [1,3,4,5,6,8,11,12,14,15,16];

def is_predecessor(i1, i2):
    if i1 == i2 - 1:
        return True;
    else:
        return False;

def make_range(i1, i2):
    if i1 == i2:
        return str(i1);
    else:
        return str(i1) + "-" + str(i2);

previous_element = None;
current_start_element = None;

for number in numbers:
    if not is_predecessor(previous_element, number):
        if current_start_element is not None:
            print make_range(current_start_element, previous_element);
        current_start_element = number;
    previous_element = number;

# handle last pair
if current_start_element is not None:
    print make_range(current_start_element, previous_element);

Это выводит:

1
3-6
8
11-12
14-16

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

Answer 6

С (гкц)

Это похоже на версию Питона .

void ranges(int n; int a[n], int n)
{
  qsort(a, n, sizeof(*a), intcmp);
  for (int i = 0; i < n; ++i) {
    const int start = i;
    while(i < n-1 and a[i] >= a[i+1]-1)
      ++i;
    printf("%d", a[start]);
    if (a[start] != a[i])
      printf("-%d", a[i]);
    if (i < n-1)
      printf(",");
  }
  printf("\n");
}

Пример:

/**
 * $ gcc -std=c99 -Wall ranges.c -o ranges && ./ranges
 */
#include <iso646.h> // and
#include <stdio.h>
#include <stdlib.h>

#define T(args...)                                              \
  {                                                             \
    int array[] = {args};                                       \
    ranges(array, sizeof(array) / sizeof(*array));              \
  }

int intcmp(const void* a, const void* b)
{
  const int *ai = a;
  const int *bi = b;

  if (*ai < *bi)
    return -1;
  else if (*ai > *bi)
    return 1;
  else
    return 0;
}

int main(void)
{
  T(1,3,4,5,6,8,11,12,14,15,16);
  T();
  T(1);
  T(1, 2);
  T(3, 1);
  T(1, 3, 4);
  T(1, 2, 4);
  T(1, 1, 2, 4);
  T(1, 2, 2, 4);
  T(1, 2, 2, 3, 5, 5);
}

Выход:

1,3-6,8,11-12,14-16

1
1-2
1,3
1,3-4
1-2,4
1-2,4
1-2,4
1-3,5

Answer 7

Python (> = 2,6)

Эта версия дополнительно обрабатывает дубликаты и несортированные последовательности.

from __future__ import print_function

def ranges(a):
    a.sort()
    i = 0
    while i < len(a):
        start = i
        while i < len(a)-1 and a[i] >= a[i+1]-1:
            i += 1
        print(a[start] if a[start] == a[i] else "%d-%d" % (a[start], a[i]),
              end="," if i < len(a)-1 else "\n")
        i += 1

Пример:

import random
r = range(10)
random.shuffle(r)
ranges(r)
ranges([1,3,4,5,6,8,11,12,14,15,16]);
ranges([])
ranges([1])
ranges([1, 2])
ranges([1, 3])
ranges([1, 3, 4])
ranges([1, 2, 4])
ranges([1, 1, 2, 4])
ranges([1, 2, 2, 4])
ranges([1, 2, 2, 3, 5, 5])

Выход:

0-9
1,3-6,8,11-12,14-16
1
1-2
1,3
1,3-4
1-2,4
1-2,4
1-2,4
1-3,5

Answer 8

Perl 6

sub to_ranges( Int *@data ){
  my @ranges;

  OUTER: for @data -> $item {
    for @ranges -> $range {
      # short circuit if the $item is in a range
      next OUTER if $range[0] <= $item <= $range[1];

      given( $item ){
        when( $range[0]-1 ){ $range[0] = $item }
        when( $range[1]+1 ){ $range[1] = $item }
      }
    }

    push @ranges, [$item,$item];
  }

  return @ranges;
}

Answer 9

module Main where

ranges :: [Int] -> [[Int]]
ranges [] = []
ranges list@(x:xs) = let adj = adjacent list in
             let len = length adj in
                 if length adj == 1
                then [[x]] ++ ranges xs
                else [[x,(last adj)]] ++ ranges (drop ((length adj) - 1) xs)
    where adjacent [] = []
          adjacent (x:xs) = if (xs /= []) && (x + 1) == head xs
             then [x] ++ adjacent (xs)
             else [x]

main = do putStrLn $ show $ ranges [1,2,3,4,5,6,8,11,12,14,15,16]

-- Output: [[1,6],[8],[11,12],[14,16]]

Вот мой лучший снимок в Хаскеле.

Answer 10

Создайте простой тип диапазона, который содержит начало / конец значений диапазона. Добавьте конструктор, который принимает только одно значение и устанавливает start = end = value. Поддерживайте стек объектов диапазона, прокладывайте отсортированную копию массива, расширяйте верхний диапазон или добавляйте новый диапазон соответствующим образом. Более конкретно, когда значение в массиве равно 1 + конечное значение для объекта диапазона в начале стека, увеличьте конечное значение для этого диапазона, если это не так, выдвиньте новый диапазон (с start = end = value в индекс в массиве) в стек.