[SOLVED] Help; algorithm to determine 'range'

b_jones10634 · #1 (**permalink**) 29-07-2010, 06:50 PM

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:

Java 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.

helloworld922 · #2 (**permalink**) 29-07-2010, 07:09 PM

simple algorithm:

Pseudo Code:

startOfCurrentRange = list[0]
lastNumber = startOfCurrentRange - 1
rangeString = startOfCurrentRange + "-"
for every number in the list:
    if number != lastNumber + 1:
        the next number is not continuous
        rangeString += lastNumber
        rangeString += ", " + number + "-"
    end if
    lastNumber = number
end for
remove last character of rangeString (it's an extra "-")

One note: You'll need to determine what the behavior should be if you have two equal numbers in the list (if this input is allowed). For example: {1, 2, 3, 3}

b_jones10634 · #3 (**permalink**) 30-07-2010, 06:05 PM

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.

b_jones10634 · #4 (**permalink**) 30-07-2010, 06:41 PM

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

Java Code:

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;

mcmillhj · #5 (**permalink**) 30-07-2010, 07:13 PM

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

Java Code

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

b_jones10634 · #6 (**permalink**) 30-07-2010, 07:33 PM

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.

helloworld922 · #7 (**permalink**) 30-07-2010, 10:31 PM

it's easy to find the start of the range: it's the smallest number in the list, and since you're list is already sorted, it's always going to be the very first element of the list (as indicated by the first line of the pseudo-code).

b_jones10634 · #8 (**permalink**) 03-08-2010, 01:49 PM

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".

b_jones10634 · #9 (**permalink**) 03-08-2010, 02:02 PM

Hunter,

Changing one line in your algoritm produces the correct result

Change this line:

Java Code

rangeString += rangeStart + "-" + previousNum;

to this:

Java Code

rangeString += rangeStart + "-" + currentNum;

mcmillhj · #10 (**permalink**) 04-08-2010, 05:58 PM

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:

Java Code

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

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

Java Code

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

What kind of errors were you getting with my solution?

Hunter

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Q:BackTracking Algorithm	Cross`17	Algorithms & Recursion	0	18-04-2010 04:33 AM
Genetic algorithm	rpsaranya	Algorithms & Recursion	2	06-03-2010 03:00 AM
set the slider's models (range)	chronoz13	AWT / Java Swing	1	29-11-2009 03:59 AM
I have algorithm problem	Newoor	What's Wrong With My Code?	3	12-11-2009 12:11 AM
algorithm	AmmrO	Algorithms & Recursion	13	25-09-2009 02:18 AM