How to convert sequence of numbers in an array to range of numbers

In javascript how to convert sequence of numbers in an array to range of numbers?

eg. [2,3,4,5,10,18,19,20] to [2-5,10,18-20]

Answers:

Answer

Here is an algorithm that I made some time ago, originally written for C#, now I ported it to JavaScript:

function getRanges(array) {
  var ranges = [], rstart, rend;
  for (var i = 0; i < array.length; i++) {
    rstart = array[i];
    rend = rstart;
    while (array[i + 1] - array[i] == 1) {
      rend = array[i + 1]; // increment the index if the numbers sequential
      i++;
    }
    ranges.push(rstart == rend ? rstart+'' : rstart + '-' + rend);
  }
  return ranges;
}

getRanges([2,3,4,5,10,18,19,20]);
// returns ["2-5", "10", "18-20"]
getRanges([1,2,3,5,7,9,10,11,12,14 ]);
// returns ["1-3", "5", "7", "9-12", "14"]
getRanges([1,2,3,4,5,6,7,8,9,10])
// returns ["1-10"]
Answer

Just having fun with solution from CMS :

  function getRanges (array) {
    for (var ranges = [], rend, i = 0; i < array.length;) {
      ranges.push ((rend = array[i]) + ((function (rstart) {
        while (++rend === array[++i]);
        return --rend === rstart;
      })(rend) ? '' : '-' + rend)); 
    }
    return ranges;
  }
Answer

I was just looking for this exact thing. I needed a PHP version so ported CMS's solution. Here it is, for anyone who stops by this question looking for the same thing:

function getRanges( $nums )
{
    $ranges = array();

    for ( $i = 0, $len = count($nums); $i < $len; $i++ )
    {
        $rStart = $nums[$i];
        $rEnd = $rStart;
        while ( isset($nums[$i+1]) && $nums[$i+1]-$nums[$i] == 1 )
            $rEnd = $nums[++$i];

        $ranges[] = $rStart == $rEnd ? $rStart : $rStart.'-'.$rEnd;
    }

    return $ranges;
}
Answer

I found this answer useful, but needed a Python version:

def GroupRanges(items):
  """Yields 2-tuples of (start, end) ranges from a sequence of numbers.

  Args:
    items: an iterable of numbers, sorted ascendingly and without duplicates.

  Yields:
    2-tuples of (start, end) ranges.  start and end will be the same
    for ranges of 1 number
  """
  myiter = iter(items)
  start = myiter.next()
  end = start
  for num in myiter:
    if num == end + 1:
      end = num
    else:
      yield (start, end)
      start = num
      end = num
  yield (start, end)


numbers = [1, 2, 3, 5, 6, 7, 8, 9, 10, 20]
assert [(1, 3), (5, 10), (20, 20)] == list(GroupRanges(numbers))
assert [(1, 1)] == list(GroupRanges([1]))
assert [(1, 10)] == list(GroupRanges([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]))
Answer

Very nice question: here's my attempt:

function ranges(numbers){
    var sorted = numbers.sort(function(a,b){return a-b;});
    var first = sorted.shift();
    return sorted.reduce(function(ranges, num){
        if(num - ranges[0][1] <= 1){
            ranges[0][1] = num;        
        } else {
            ranges.unshift([num,num]);
        }
        return ranges;
    },[[first,first]]).map(function(ranges){
        return ranges[0] === ranges[1] ? 
            ranges[0].toString() : ranges.join('-');
    }).reverse();
}

Demo on JSFiddler

Answer

If you simply want a string that represents a range, then you'd find the mid-point of your sequence, and that becomes your middle value (10 in your example). You'd then grab the first item in the sequence, and the item that immediately preceded your mid-point, and build your first-sequence representation. You'd follow the same procedure to get your last item, and the item that immediately follows your mid-point, and build your last-sequence representation.

// Provide initial sequence
var sequence = [1,2,3,4,5,6,7,8,9,10];
// Find midpoint
var midpoint = Math.ceil(sequence.length/2);
// Build first sequence from midpoint
var firstSequence = sequence[0] + "-" + sequence[midpoint-2];
// Build second sequence from midpoint
var lastSequence  = sequence[midpoint] + "-" + sequence[sequence.length-1];
// Place all new in array
var newArray = [firstSequence,midpoint,lastSequence];

alert(newArray.join(",")); // 1-4,5,6-10

Demo Online: http://jsbin.com/uvahi/edit

Answer

Here is a version for Perl:

use strict;
use warnings;

my @numbers = (0,1,3,3,3,4,4,7,8,9,12, 14, 15, 19, 35, 35, 37, 38, 38, 39);
@numbers =  sort {$a <=> $b} @numbers ; # Make sure array is sorted.

# Add "infinity" to the end of the array.
$numbers[1+$#numbers] = undef ;

my @ranges = () ; # An array where the range strings are stored.

my $start_number = undef ;
my $last_number  = undef ;
foreach my $current_number (@numbers)
{
  if (!defined($start_number))
  {
    $start_number = $current_number ;
    $last_number  = $current_number ;
  }
  else
  {
    if (defined($current_number) && (($last_number + 1) >= $current_number))
    {
      $last_number = $current_number ;
      next ;
    }
    else
    {
      if ($start_number == $last_number)
      {
        push(@ranges, $start_number) ;
      } 
      else
      {
        push(@ranges, "$start_number-$last_number") ;
      }
      $start_number = $current_number ;
      $last_number  = $current_number ;
    }
  }
}

# Print the results
print join(", ", @ranges) . "\n" ; 
# Returns "0-1, 3-4, 7-9, 12, 14-15, 19, 35, 37-39"
Answer

Here's my take on this...

function getRanges(input) {

  //setup the return value
  var ret = [], ary, first, last;

  //copy and sort
  var ary = input.concat([]);
  ary.sort(function(a,b){
    return Number(a) - Number(b);
  });

  //iterate through the array
  for (var i=0; i<ary.length; i++) {
    //set the first and last value, to the current iteration
    first = last = ary[i];

    //while within the range, increment
    while (ary[i+1] == last+1) {
      last++;
      i++;
    }

    //push the current set into the return value
    ret.push(first == last ? first : first + "-" + last);
  }

  //return the response array.
  return ret;
}
Answer

In C#

    public string compressNumberRange(string inputSeq)
    {
        //Convert String array to long List and removing the duplicates
        List<long> longList = inputSeq.Split(',').ToList().ConvertAll<long>(s => Convert.ToInt64(s)).Distinct().ToList();

        //Sort the array
        longList.Sort();

        StringBuilder builder = new StringBuilder();


        for (int itr = 0; itr < longList.Count(); itr++)
        {
            long first = longList[itr];
            long end = first;

            while (longList[itr + 1] - longList[itr] == 1) //Seq check 
            {
                end = longList[itr + 1];
                itr++;
                if (itr == longList.Count() - 1)
                    break;
            }
            if (first == end) //not seq
                builder.Append(first.ToString() + ",");
            else //seq
                builder.Append(first.ToString() + "-" + end.ToString() + ",");
        }

        return builder.ToString();
    }
Answer

Here is a port of CMS's code for BASH:

#!/usr/bin/env bash
# vim: set ts=3 sts=48 sw=3 cc=76 et fdm=marker: # **** IGNORE ******
get_range() { RANGE= # <-- OUTPUT                  **** THIS   ******
   local rstart rend i arr=( "[email protected]" )  # ported from **** JUNK   ******
   for (( i=0 ; i < $# ; i++ )); do  # http://stackoverflow.com
      (( rstart = arr[i] ))          # /a/2270987/912236
      rend=$rstart; while (( arr[i+1] - arr[i] == 1 )); do
      (( rend = arr[++i] )); done; (( rstart == rend )) &&
   RANGE+=" $rstart" || RANGE+=" $rstart-$rend"; done; } # }}}
Answer

You could iterate over the numbers and see if the next number is 1 bigger then the current number. So have a:

struct range {
    int start;
    int end;
} range;

where if array[i+1] == array[i]+1; (where i is the currently observed number) then range.end = array[i+1];. Then you progress to the next i; If array[i+1] != array[i]+1; then range.end = array[i];

you could store the ranges in a vector< range > ranges;

printing would be easy:

for(int i = 0; i < ranges.size(); i++) {
    range rng = (range)ranges.at(i);
    printf("[%i-%i]", rng.start, rng.end);
}
Answer
 ; For all cells of the array
    ;if current cell = prev cell + 1 -> range continues
    ;if current cell != prev cell + 1 -> range ended

int[] x  = [2,3,4,5,10,18,19,20]
string output = '['+x[0]
bool range = false; --current range
for (int i = 1; i > x[].length; i++) {
  if (x[i+1] = [x]+1) {
    range = true;
  } else { //not sequential
  if range = true
     output = output || '-' 
  else
     output = output || ','
  output.append(x[i]','||x[i+1])
  range = false;
  } 

}

Something like that.

Answer

PHP

function getRanges($nums) {
sort($nums);
$ranges = array();

for ( $i = 0, $len = count($nums); $i < $len; $i++ )
{
    $rStart = $nums[$i];
    $rEnd = $rStart;
    while ( isset($nums[$i+1]) && $nums[$i+1]-$nums[$i] == 1 )
        $rEnd = $nums[++$i];

    $ranges[] = $rStart == $rEnd ? $rStart : $rStart.'-'.$rEnd;
}

return $ranges;
}


echo print_r(getRanges(array(2,21,3,4,5,10,18,19,20)));
echo print_r(getRanges(array(1,2,3,4,5,6,7,8,9,10)));
Answer
import java.util.ArrayList;
import java.util.Arrays;



public class SequencetoRange {

    /**
     * @param args
     */
    public static void main(String[] args) {
    // TODO Auto-generated method stub

        int num[] = {1,2,3,63,65,66,67,68,69,70,80,90,91,94,95,4,101,102,75,76,71};

        int l = num.length;
        int i;
        System.out.print("Given number : ");
        for (i = 0;i < l;i++ ){
            System.out.print("  " + num[i]);
        }
        System.out.println("\n");
        Arrays.sort(num);

        ArrayList newArray = new ArrayList();
        newArray = getRanges(num);
        System.out.print("Range : ");
        for(int y=0;y<newArray.size();y++)
        {
            System.out.print(" " +newArray.get(y));
        }
    }

    public static ArrayList getRanges(int num[])
    {  
        ArrayList ranges = new ArrayList();
        int rstart, rend;   
        int lastnum = num[num.length-1];
        for (int i = 0; i < num.length-1; i++) 
        {     
            rstart = num[i];     
            rend = rstart;     
            while (num[i + 1] - num[i] == 1) 
            {       
                rend = num[i + 1]; 
                // increment the index if the numbers sequential       
                if(rend>=lastnum)
                {
                    break;
                }
                else
                {
                    i++;
                }  
            }  
            if(rstart==rend)
            {
                ranges.add(rend);
            }
            else
            {
                ranges.add(+rstart+"..."+rend);
            }
        } 
        return ranges; 
    } 
}
Answer

I've written my own method that's dependent on Lo-Dash, but doesn't just give you back an array of ranges, rather, it just returns an array of range groups.

[1,2,3,4,6,8,10] becomes:

[[1,2,3,4],[6,8,10]]

http://jsfiddle.net/mberkom/ufVey/

Answer

An adaptation of CMS's javascript solution for Cold Fusion

It does sort the list first so that 1,3,2,4,5,8,9,10 (or similar) properly converts to 1-5,8-10.

<cfscript>
    function getRanges(nArr) {
        arguments.nArr = listToArray(listSort(arguments.nArr,"numeric"));
        var ranges = [];
        var rstart = "";
        var rend = "";
        for (local.i = 1; i <= ArrayLen(arguments.nArr); i++) {
            rstart = arguments.nArr[i];
            rend = rstart;
            while (i < ArrayLen(arguments.nArr) and (val(arguments.nArr[i + 1]) - val(arguments.nArr[i])) == 1) {
                rend = val(arguments.nArr[i + 1]); // increment the index if the numbers sequential
                i++;
            }
            ArrayAppend(ranges,rstart == rend ? rstart : rstart & '-' & rend);
        }
        return arraytolist(ranges);
    }
</cfscript>
Answer

Here's what I put together in Swift. It eliminates duplicates and sorts the array first, and doesn't mind if it's given an empty array or an array of one.

func intArrayToString(array: [Int]) -> String {
    var intArray = Array(Set(array))
    intArray.sortInPlace()
    if intArray.count == 0 {
        return ""
    }
    var intString = "\(intArray[0])"
    if intArray.count > 1 {
        for j in 1..<intArray.count-1 {
            if intArray[j] == intArray[j-1]+1 {
                if intArray[j] != intArray[j+1]-1 {
                    intString += "-\(intArray[j])"
                }
            } else {
                intString += ",\(intArray[j])"
            }
        }
        if intArray.last! == intArray[intArray.count-2]+1 {
            intString += "-\(intArray.last!)"
        } else {
            intString += ",\(intArray.last!)"
        }
    }
    return intString
}
Answer

Tiny ES6 module for you guys. It accepts a function to determine when we must break the sequence (breakDetectorFunc param - default is the simple thing for integer sequence input). NOTICE: since input is abstract - there's no auto-sorting before processing, so if your sequence isn't sorted - do it prior to calling this module

function defaultIntDetector(a, b){
    return Math.abs(b - a) > 1;
}

/**
 * @param {Array} valuesArray
 * @param {Boolean} [allArraysResult=false] if true - [1,2,3,7] will return [[1,3], [7,7]]. Otherwise [[1.3], 7]
 * @param {SequenceToIntervalsBreakDetector} [breakDetectorFunc] must return true if value1 and value2 can't be in one sequence (if we need a gap here)
 * @return {Array}
 */
const sequenceToIntervals = function (valuesArray, allArraysResult, breakDetectorFunc) {
    if (!breakDetectorFunc){
        breakDetectorFunc = defaultIntDetector;
    }
    if (typeof(allArraysResult) === 'undefined'){
        allArraysResult = false;
    }

    const intervals = [];
    let from = 0, to;
    if (valuesArray instanceof Array) {
        const cnt = valuesArray.length;
        for (let i = 0; i < cnt; i++) {
            to = i;
            if (i < cnt - 1) { // i is not last (to compare to next)
                if (breakDetectorFunc(valuesArray[i], valuesArray[i + 1])) {
                    // break
                    appendLastResult();
                }
            }
        }
        appendLastResult();
    } else {
        throw new Error("input is not an Array");
    }

    function appendLastResult(){
        if (isFinite(from) && isFinite(to)) {
            const vFrom = valuesArray[from];
            const vTo = valuesArray[to];

            if (from === to) {
                intervals.push(
                    allArraysResult
                        ? [vFrom, vTo] // same values array item
                        : vFrom // just a value, no array
                );
            } else if (Math.abs(from - to) === 1) { // sibling items
                if (allArraysResult) {
                    intervals.push([vFrom, vFrom]);
                    intervals.push([vTo, vTo]);
                } else {
                    intervals.push(vFrom, vTo);
                }
            } else {
                intervals.push([vFrom, vTo]); // true interval
            }
            from = to + 1;
        }
    }

    return intervals;
};

module.exports = sequenceToIntervals;

/** @callback SequenceToIntervalsBreakDetector
 @param value1
 @param value2
 @return bool
 */

first argument is the input sequence sorted array, second is a boolean flag controlling the output mode: if true - single item (outside the intervals) will be returned as arrays anyway: [1,7],[9,9],[10,10],[12,20], otherwise single items returned as they appear in the input array

for your sample input

[2,3,4,5,10,18,19,20]

it will return:

sequenceToIntervals([2,3,4,5,10,18,19,20], true) // [[2,5], [10,10], [18,20]]
sequenceToIntervals([2,3,4,5,10,18,19,20], false) // [[2,5], 10, [18,20]]
sequenceToIntervals([2,3,4,5,10,18,19,20]) // [[2,5], 10, [18,20]]
Answer

Using ES6, a solution is:

function display ( vector ) { // assume vector sorted in increasing order
    // display e.g.vector [ 2,4,5,6,9,11,12,13,15 ] as "2;4-6;9;11-13;15"
    const l = vector.length - 1; // last valid index of vector array
    // map [ 2,4,5,6,9,11,12,13,15 ] into array of strings (quote ommitted)
    // --> [ "2;", "4-", "-", "6;", "9;", "11-", "-", "13;", "15;" ]
    vector = vector.map ( ( n, i, v ) => // n is current number at index i of vector v
        i < l && v [ i + 1 ] - n === 1 ? // next number is adjacent ? 
            `${ i > 0 && n - v [ i - 1 ] === 1 ? "" : n }-` :
            `${ n };`
        );
    return vector.join ( "" ).  // concatenate all strings in vector array
        replace ( /-+/g, "-" ). // replace multiple dashes by single dash
        slice ( 0, -1 );        // remove trailing ;
    }

If you want to add extra spaces for readability, just add extra calls to string.prototype.replace().

If the input vector is not sorted, you can add the following line right after the opening brace of the display() function:

vector.sort ( ( a, b ) => a - b ); // sort vector in place, in increasing order.

Note that this could be improved to avoid testing twice for integer adjacentness (adjacenthood? I'm not a native English speaker;-).

And of course, if you don't want a single string as output, split it with ";".

Answer

I needed a PHP version that also supports downward ranges (e.g. [10,9,8] gets converted to [10-8]). So I have modified DisgruntledGoat's version who ported CMS's solution. It also handles Strings in the input properly.

function getRanges($nums)
{
    $ranges = array();

    for ($i = 0; $i < count($nums); $i++) {
        if (!is_numeric($nums[$i]) || !isset($nums[$i+1]) || !is_numeric($nums[$i+1])) {
            $ranges[] = $nums[$i];
            continue;
        }
        $rStart = $nums[$i];
        $rEnd = $rStart;
        $rDiff = $nums[$i+1] > $nums[$i] ? 1 : -1;
        while (isset($nums[$i+1]) && is_numeric($nums[$i+1]) && $nums[$i+1]-$nums[$i] == $rDiff)
            $rEnd = $nums[++$i];
        $ranges[] = $rStart == $rEnd ? $rStart : $rStart.'-'.$rEnd;
    }

    return $ranges;
}

Example:

getRanges([2,3,4,5,10,18,19,20,"downwards",10,9,8,7,6,5])
// Returns [2-5,10,18-20,"downwards",10-5]
Answer

I needed TypeScript code today to solve this very problem -- many years after the OP -- and decided to try a version written in a style more functional than the other answers here. Of course, only the parameter and return type annotations distinguish this code from standard ES6 JavaScript.

  function toRanges(values: number[],
                    separator = '\u2013'): string[] {
    return values
      .slice()
      .sort((p, q) => p - q)
      .reduce((acc, cur, idx, src) => {
          if ((idx > 0) && ((cur - src[idx - 1]) === 1))
            acc[acc.length - 1][1] = cur;
          else acc.push([cur]);
          return acc;
        }, [])
      .map(range => range.join(separator));
  }

Note that slice is necessary because sort sorts in place and we can't change the original array.

Answer

Here's a version in Coffeescript

getRanges = (array) -> 
    ranges = []
    rstart
    rend
    i = 0
    while  i < array.length
      rstart = array[i]
      rend = rstart
      while array[i + 1] - array[i] is 1
        rend = array[i + 1] # increment the index if the numbers sequential
        i = i  + 1
      if rstart == rend 
        ranges.push  rstart + ''
      else
        ranges.push rstart + '-' + rend
      i = i + 1
    return ranges
Answer

I just made an npm package for it. sequence-to-range

https://www.npmjs.com/package/sequence-to-range

Tags

Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.