Thread: Help; algorithm to determine 'range'

Hello community,

I'm trying to develop a function to determine the 'range' of some integer values. 'Range' is the best way I can describe it, but it is different than the mathematical 'range', which is simply the absolute of the highest value minus the absolute of the lowest value.

It's best to describe with an example.

Lets say I have a list of Integers (pre sorted), containing values [2, 3, 4, 7, 8, 9, 14, 16, 18, 19, 20].

I need to build a string that describes the 'ranges' found within these values. So, for the above list of integers, the corresponding 'range' string would be "2-4, 7-9, 14, 16, 18-20".

I spent the afternoon here trying to create a function that would accomodate this requirement, but I can't seem to develop it in a way that will acount for all possible scenarios.

Following is my (not quite working) code:

Collections.sort( channelNums );
String channelRange = "";
int previousNum = 0;
boolean x = false;
 
for( int i = 0; i < channelNums.size(); i++ )
{
	int currentNum = channelNums.get( i ).intValue();
 
	if( i == 0 )
		channelRange = Integer.toString( currentNum );
	else
	{
		if( currentNum == (previousNum + 1) )
		{
			x = true;
			if( !channelRange.endsWith( "-" ) )
				channelRange += "-";
		}
		else
			channelRange += ", " + Integer.toString( currentNum );
	}
 
	previousNum = currentNum;
}
 
if( x )
	channelRange += Integer.toString( previousNum );

Any input would be highly appreciated. Thanks in advance.

Thanks for your reply, unfortunately the algorithm you supplied does not account for all scenarios (it assumes that it will always start with a range, but what if the set is [6, 8, 10, 14, 18]).

And, FYI, for the scope of my project, the list of integers will NEVER have duplicate values.

I think I've developed an algorithm that accounts for all necessary scenarios.
Any comments are welcomed.

int startOfCurrentRange = channelNums.get( 0 ).intValue();
int lastNumber = startOfCurrentRange - 1;
String channelRange = startOfCurrentRange + "-";
for( int i = 0; i < channelNums.size(); i++ )
{
 
	int currentNumber = channelNums.get( i ).intValue();
	if( currentNumber != (lastNumber + 1) )
	{
		if( channelRange.charAt( channelRange.length() - 1 ) == '-' )
			channelRange = channelRange.substring( 0, channelRange.length() - 1 );
 
		if( Integer.parseInt( Character.toString( channelRange.charAt( channelRange.length() - 1 ) ) ) == lastNumber )
			channelRange += ", " + currentNumber + "-";
		else
			channelRange += "-" + lastNumber + ", " + currentNumber + "-";
	}
 
	if( i == channelNums.size() -1 )
		channelRange += currentNumber;
 
	lastNumber = currentNumber;
}
 
// Remove trailing '-'
if( channelRange.charAt( channelRange.length() - 1 ) == '-' )
	channelRange = channelRange.substring( 0, channelRange.length() - 1 );
 
// Remove trailing single channel range (ex. replace traling '12-12' with '12')
if( channelRange.substring( (channelRange.length() - (Integer.toString( lastNumber ).length() * 2 + 1)), channelRange.length() )
	.compareToIgnoreCase( Integer.toString( lastNumber ) + "-" + Integer.toString( lastNumber ) ) == 0 )
		channelRange = channelRange.substring( 0, (channelRange.length() - (Integer.toString( lastNumber ).length() * 2 + 1)) ) +
			lastNumber;

I wrote this one, I think mine is a little simpler than yours. Let me know what you think.

public class TestRange
{
	public static void main(String[] args)
	{
		int[] intArray = {2,3,4,7,9,10,11,15,16,19};
		String rangeString = "";
 
		//first element in the array
		int last = intArray[0];
		int current = 0;
		int rangeStart = -1;
 
		for(int i = 1; i <= intArray.length - 1; i++)
		{
			//assign the current number
			current = intArray[i];
 
			//test for range
			if ( current != (last+1) )
			{
				//if there is a range append it to the rangeString
				if(rangeStart != -1)
				{
					rangeString +=  rangeStart + "-" + last + ", ";
 
					//reset the range start variable
					rangeStart = -1;
				}
				else //if there isnt a range add the individual int to the rangeString
				{
					rangeString += last + ", ";
				}
 
				if( i == (intArray.length-1))
					rangeString += current;
			}
			else
			{
				//if there are consecutive numbers, store the starting number
				if( rangeStart == -1)
					rangeStart = last;
 
				//if this is the last element append any remaining ranges
				if( i == (intArray.length-1))
					rangeString +=rangeStart + "-" + last;
			}
			//assign the new last variable
			last = current;
		}
 
		//print rangeString
		System.out.println("rangeString: " + rangeString);
	}
}

This was my output:
rangeString: 2-4, 7, 9-11, 15-16, 19

Hunter

Hey Hunter,

Thanks for your input, your solution does seem slightly less convoluted. I wasn't particular happy with my solution based on all the string comparisons and substrings.

I think I'll give yours a go and see how it works out.

Thanks again.

HelloWorld,

Thanks for your reply, but I'm not sure you understood the problem at hand.

The task is not to find the start of the range... yes that is very easy to accomplish.
The task is to find the range of values in the given list. Your pseudo code attempts to satisfy this problem, but does not account for all scenarios.

For instance, your pseudo code algorithm assumes that the list of numbers will always start with a range of values (ex. [1, 2, 4, 5, 8]), but one of the most simples cases may incorporate a series that does NOT start with a range (ex. [1, 4, 5, 6, 9]).

A more suitable approach is to utilize the method either Hunter or I developed.

Further more, Hunter, your algorithm is very straight forward, however I found one small problem. The last range in the value is alwas 1 LESS than the actual value. For instance, if the series is [1, 2, 3, 4, 5], your algorithm will produce the range string = "1-4".

Hunter,

Changing one line in your algoritm produces the correct result

Change this line:

rangeString += rangeStart + "-" + previousNum;

to this:

rangeString += rangeStart + "-" + currentNum;

When I make the change you suggest my algorithm actually does not work.

with this input and your suggested change: {2,3,4,9,11,12,13,16,19,19}

I get this output:

rangeString: 2-9, 9, 11-16, 16, 19, 19

With no changes I get this (which is correct):

rangeString: 2-4, 9, 11-13, 16, 19, 19

What kind of errors were you getting with my solution?

Hunter

just for fun, in scala it would be:

  def main(args: Array[String]) {
    val test = List(2,3,4,9,11,12,13,16,19,19,19,19,21,22,23,24)
    val result = {
      //get the ranges. add an artificial "end marker" that will be dropped after the algorithm finished
      val listAndEndMarker = test :+ test.max + 2
      val firstElement = List(test.head)
      val ranges = (firstElement /: listAndEndMarker.sliding(2, 1))((result, currentTuple) => {
        //if the difference is > 1, add the current tuple to the result list
        if (currentTuple.last - 1 > currentTuple.head) result ++ currentTuple else result
      }).dropRight(1)
      //format them
      ranges.sliding(2, 2).map(e => if (e.head < e.last) e.head + "-" + e.last else e.head.toString).toList
    }
    println(result)
  }

this can even be written a bit shorter by inlining the vals. the output is List(2-4, 9, 11-13, 16, 19, 21-24)

Hunter,

When I implemented your solution, the results would be near perfect, expect the last number in the string would actually be the second last number in the list of integers.

I'm not sure why we are getting differing results, the only difference is that you're using an array, where I'm using a List.

With the change I mentioned, I now get the correct results.

// Starting values
		String retVal = "";
		int previousNum = numberList.get( 0 );
		int currentNum = 0;
		int rangeStart = -1;
 
		// For each number in the list (excluding the first number which was accessed above)
		for(int i = 1; i <= numberList.size() - 1; i++)
		{
			// Assign the current number
			currentNum = numberList.get( i );
 
			// Test for range
			if ( currentNum != (previousNum + 1) )
			{
				// If there is a range append it to the channelRange
				if( rangeStart != -1 )
				{
					retVal +=  rangeStart + "-" + previousNum + ", ";
 
					// Reset the range start variable
					rangeStart = -1;
				}
 
				// If there isnt a range add the individual int to the channelRange
				else
					retVal += previousNum + ", ";
 
				if( i == (numberList.size() - 1) )
					retVal += currentNum;
			}
			else
			{
				// If there are consecutive numbers, store the starting number
				if( rangeStart == -1 )
					rangeStart = previousNum;
 
				// If this is the last element append any remaining ranges
				if( i == (numberList.size() - 1) )
					retVal += rangeStart + "-" + currentNum;
			}
 
			// Assign the new last number
			previousNum = currentNum;
		}

Thanks for pointing that out. I wasn't seeing it in my test because the last two numbers in my data set were the same.

Hunter

byte[]array=new byte[10];
		for(byte i=0;i<10;i++){
			array[i]=(byte)((i*2)+(2*Math.random()));
			System.out.println(array[i]);
		}
		boolean even=false;
		byte next=0,range;
		List<Byte>ranges=new ArrayList<Byte>();
		for(byte i=0;i<10;i++){
			if(i<next){
				i=next;
			}
			else{
				if(array[i]%2==0)even=true;
				else even=false;
				if(even==true){
					next=(byte)(i+1);
					while(next<10){	
						if(array[next]%2==0)break;
						next++;
					}
					if(next==10)next=(byte)(i+1);
				}
				if(even==false){
					next=(byte)(i+1);
					while(next<10){
						if(array[next]%2==1)break;
						next++;
					}
					if(next==10)next=(byte)(i+1);
				}
			}
			ranges.add((byte)i);
		}
		for(byte i=0;i<ranges.size();i++){
			if(i==0)System.out.print(array[ranges.get(0)]);
			if(i>0){
				if(ranges.get(i)-ranges.get(i-1)>1)System.out.print("-"+array[ranges.get(i)]);
				else System.out.print(", "+array[ranges.get(i)]);	
			}
		}
		System.out.println();

You need to import java.util.*; The code can go straight into main method. I was too lazy to make a sort method so I just made a series of random numbers that are definitely bigger than the previous one and put it into an array. Everytime it's different. Feel free to ask any questions. I did not add documentation, but to generalize:

-The first loop gets the array data
-The second loop makes a list of all beginnings and ends of odds and evens in the range form that you specified. I don't know how to explain that, but I'm 99% sure this is what you need.
-The last loop just outputs the values in the way that you wanted.

As a side note, I used byte because it's smaller than int, that's why you see (byte) everywhere if you didn't know. If you change it to int you may not have to do that.