How would you display an array of integers as a set of ranges? (algorithm)

Question

Given an array of integers, what is the simplest way to iterate over it and figure out all the ranges it covers? for example, for an array such as:

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

The ranges would be:

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

Answer 1

Here's a python implementation, it should be easy enough to follow

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

This outputs:

1
3-6
8
11-12
14-16

I know, I know, it isn't an algorithm, but I found it harder to actually explain it without having indentation problems than to just implement a solution for it.

Answer 2

If the array is sorted in ascending order, then the problem is easy. Define a Range structure or class, which has a beginning and an end. Then go through the array. If the current element is one more than the previous, update Range.end, otherwise create a new range with this element as Range.begin. Store the ranges to a dynamic array or a linked list. Or just print them out as you go.

If the array may not be sorted, then sort it first.

Answer 3

first: sort second: tokenise then: print the first value and loop over subsequent ones. If the 'current' value is equal to the last value +1, skip it. Otherwise if you've skipped value print dash and the value, otherwise print a comma and repeat.

That should do. Unless you wanted me to code up your homework for you? :)

Answer 4

Assuming the list is ordered you could start at the end and keep subtracting the next one down. While the difference is 1, you're in a range. When it's not, you start a new range.

i.e

16-15 = 1

15-14 = 1

14-12 = 2, the range is 16-14 - start a new range.

Answer 5

startRange = array[0];    
for(i=0;i<array.length;i++)
{
   if (array[i + 1] - array[i] > 1)
   {
     endRange = array[i];
     pushRangeOntoArray(startRange,endRange);
     i++;
     startRange = array[i]
     // need to check for end of array here
   }
}

Answer 6

Here's my Perl solution. Could be cleaner and faster, but it shows how it works:

# Just in case it's not sorted...
my @list = sort { $a <=> $b } ( 1, 3, 4, 5, 6, 8, 11, 12, 14, 15, 16 );

my $range = [ $list[0] ];

for(@list[1 .. $#list]) {
    if($_ == $range->[-1] + 1) {
        push @$range, $_;
    }
    else {
        print $#$range ? $range->[0] . '-' . $range->[-1] : $range->[0], "\n";
        $range = [ $_ ];
    }
}

Answer 7

My solution in Java 1.5 would be:

public static List<String> getRanges(int... in) {
 List<String> result = new ArrayList<String>();
 int last = -1;
 for (int i : in) {
  if (i != (last + 1)) {
   if (!result.isEmpty()) {
    addRange(result, last);
   }
   result.add(String.valueOf(i));
  } 
  last = i;
 }
 addRange(result, last);
 return result;
}

private static void addRange(List<String> result, int last) {
 int lastPosition = result.size() - 1;
 String lastResult = result.get(lastPosition);
 if (!lastResult.equals(String.valueOf(last))) {
  result.set(lastPosition, lastResult + "-" + last);
 }
}

public static void main(String[] args) {
 List<String> ranges = getRanges(1, 3, 4, 5, 6, 8, 11, 12, 14, 15, 16);
 System.out.println(ranges);
}

which outputs:

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

Greetz, GHad

Answer 8

I believe the mergeinfo property that was introduced to Subversion in the 1.5 release has a format that is the same as what you're asking for, so you could potentially go look through the source of Subversion to find out how they do it. I'd be surprised if its any different than the other suggestions that have already been posted here.

Answer 9

If the array is sorted, as in your example, I would define buckets containing a min and a max.

Initialize: Create a bucket with a min and a max equal to the first value.

Loop: Compare each value with the max of the current bucket. If it is equal to or 1 more than the current max, update the max. If it is more than 1 greater than the max, save the bucket to a list of buckets and start a new bucket.

At the end you will have a set of buckets with a min and a max in each. If the min is the same as the max, print a single number (ie: in your example, the first bucket would have a min and a max of 1). If they are different, print as a range.

Example implementation in 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>

Basically you end up with a list of things, where each thing has (lowest-in-bucket, highest-in-bucket). Those are your ranges.

If the list is not already sorted, sort it first.

Answer 10

I will assume the array X() is pre-sorted (and if not, sort the array before-hand).

for each element of X() as $element (with $i as current array posistion)
    add $element to end of array Y()
    if (X($i) + 1 is less than X($i + 1)) AND ($i + 1 is not greater than sizeof(X())) then
        append Y(1)."-".Y(sizeof(Y())) to end of Z()
        unset Y()
    end if    
next
if anything remains in Y() append to end of Z()

well, that's how I would do it.

Answer 11

Create a simple range type which contains start / end of range values. Add a constructor which takes only one value and sets start = end = value. Maintain a stack of range objects, work your way through a sorted copy of the array, extend the top range or add a new range as appropriate. More specifically, when the value in the array is 1 + the end value for the range object on the to of the stack, increment the end value for that range, when it's not, push a new range (with start = end = value at index in array) onto the stack.

Answer 12

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]]

Here's my best shot in Haskell.

Answer 13

Here's a C# 3.0'y way of doing it:

Points of interest:

• automatic properties (public int Property { get; set; })
• using new object initializers (new Range { Begin = xxx; ... }
• using yield for lazy evaluation
• using linq extension methods (First() and 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;
    }
}

Cheers, David

Answer 14

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 15

Python (>= 2.6)

This version additionally handles duplicates and unsorted sequences.

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

Example:

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

Output:

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 16

C (gcc)

It is similar to the Python's version.

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

Example:

/**
 * $ 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);
}

Output:

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