Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 14 of 14

Thread: Help; algorithm to determine 'range'

  1. #1
    Junior Member
    Join Date
    Jul 2010
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

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


  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Help; algorithm to determine 'range'

    simple algorithm:

    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}

  3. #3
    Junior Member
    Join Date
    Jul 2010
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help; algorithm to determine 'range'

    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.

  4. #4
    Junior Member
    Join Date
    Jul 2010
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help; algorithm to determine 'range'

    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;

  5. #5
    Junior Member
    Join Date
    Jul 2010
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help; algorithm to determine 'range'

    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

  6. #6
    Junior Member
    Join Date
    Jul 2010
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help; algorithm to determine 'range'

    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.

  7. #7
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Help; algorithm to determine 'range'

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

  8. #8
    Junior Member
    Join Date
    Jul 2010
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help; algorithm to determine 'range'

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

  9. #9
    Junior Member
    Join Date
    Jul 2010
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help; algorithm to determine 'range'

    Hunter,

    Changing one line in your algoritm produces the correct result

    Change this line:

    rangeString += rangeStart + "-" + previousNum;

    to this:

    rangeString += rangeStart + "-" + currentNum;

  10. #10
    Junior Member
    Join Date
    Jul 2010
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help; algorithm to determine 'range'

    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

  11. #11
    Junior Member
    Join Date
    Aug 2010
    Posts
    19
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help; algorithm to determine 'range'

    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)

  12. #12
    Junior Member
    Join Date
    Jul 2010
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help; algorithm to determine 'range'

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

  13. #13
    Junior Member
    Join Date
    Jul 2010
    Posts
    6
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Help; algorithm to determine 'range'

    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

  14. #14
    Junior Member
    Join Date
    Jun 2010
    Posts
    26
    Thanks
    3
    Thanked 0 Times in 0 Posts

    Default Re: Help; algorithm to determine 'range'

    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.

Similar Threads

  1. Q:BackTracking Algorithm
    By Cross`17 in forum Algorithms & Recursion
    Replies: 0
    Last Post: April 18th, 2010, 12:33 AM
  2. Genetic algorithm
    By rpsaranya in forum Algorithms & Recursion
    Replies: 2
    Last Post: March 5th, 2010, 11:00 PM
  3. set the slider's models (range)
    By chronoz13 in forum AWT / Java Swing
    Replies: 1
    Last Post: November 28th, 2009, 11:59 PM
  4. I have algorithm problem
    By Newoor in forum What's Wrong With My Code?
    Replies: 3
    Last Post: November 11th, 2009, 08:11 PM
  5. algorithm
    By AmmrO in forum Algorithms & Recursion
    Replies: 13
    Last Post: September 24th, 2009, 10:18 PM