Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Having

  • a minimum
  • a maximum
  • number of ranges
  • a value between minimum and maximum

I'm trying to come up with a method, or two, which would calculate which range the provided value belongs to.

For min=1, max = 10, number of ranges=5 the ranges would be [1,2],[3,4],[5,6],[7,8],[9-10]

The other method would behave like shown below:

  • method(1)->[1-2]
  • method(2)->[1-2]
  • method(3)->[3-4]
  • method(4)->[3-4]
  • method(5)->[5-6]
  • method(6)->[5-6]
  • method(7)->[7-8]
  • method(8)->[7-8]
  • method(9)->[9-10]
  • method(10)->[9-10]

This would be used for generating a legend for a map where the size of the marker depends on the range a value belongs to.

I wonder if there is a nice algorithmic solution for this.

The numbers I work with are integers.

Edit:

Another example:

For min=1, max = 3, number of ranges=2 the ranges would be

a) [1-2],[3-3]

or

b) [1-1],[2-3]

The other method would behave like shown below:

a)

  • method(1)->[1-2]
  • method(2)->[1-2]
  • method(3)->[3-3]

or b)

  • method(1)->[1-1]
  • method(2)->[2-3]
  • method(3)->[2-3]

I don't have a preference for a) or b).

share|improve this question
    
Basically, you want division. If the ratio between number and range size is smaller than 1, it goes into the first bin, etc. (OK, if your range doesn't start from 0, then you have to subtract the offset from both first, but that's it.) –  Kilian Foth Feb 20 '13 at 8:48
1  
Are the ranges necessarily of equal length? Could I choose the ranges [1-3], [4-10], or is that not an option? If they're of equal length, then this is a pretty simple division problem, as Killian said above. If not, you need actual searching of ranges - playing with a binary tree would be an obvious option. –  Standback Feb 20 '13 at 10:28
    
Yes, I'm after ranges of equal length when possible (for range 1-3 and number of ranges 2 it would not be possible and it's ok). –  Tymek Feb 22 '13 at 5:31
add comment

2 Answers

Let n be the number of ranges. If you can divide your range into equal subranges, you can do it like this:

length_of_range = (max - min + 1) / n

For i = 1 to n:
start_of_range(i) = length_of_range * (i-1) + min  
end_of_range(i) = start_of_range(i) + length_of_range - 1   

method(number) = (number - min) / length_of_range + 1   // '/' is integer division

If you can't divide them into equal subranges, the first (max - min + 1) % n subranges should have length ((max - min + 1) / n) + 1 and the rest should have length (max - min + 1) / n. Knowing that, you should be able to adjust the above formulas yourself.

share|improve this answer
    
Thanks, but for min=1 and max=9 length_of_range would be 1 which is not correct. –  Tymek Feb 21 '13 at 1:09
    
You can't have min = 1 and max = 9 (and number of ranges = 5) if you want to divide your range into subranges of equal length. If that's not what you're looking for, you'll have to explain what is it that you're looking for more precisely. Until then, -1 for being too unclear (and not answering Standback's question). –  iCanLearn Feb 21 '13 at 8:27
    
I forgot to say that your code would also not work if the range would be [10-19] or any range that doesn't start at 0. –  Tymek Feb 22 '13 at 5:40
    
@Tymek: There's a very simple way to translate the [10-19] problem into a [0-9] problem: subtract 10 from the min and max. To get it back, just add 10 back. –  Michael Shaw Feb 22 '13 at 20:40
    
@MichaelShaw This was missing in the original answer and has been kindly adjusted. –  Tymek Feb 25 '13 at 2:27
add comment

Here's what I would do:

First start with an array the size of number of ranges to keep track of the length of each range. Let's call this bucket_sizes[number_of_ranges]

  1. Initialize the size of each bucket with the highest evenly possible length: (max-min+1)/number_of_ranges (integer division)
  2. Then, find the surplus that couldn't fit evenly in each bucket, (max-min+1) % number_of_ranges (remainder from integer division)
  3. Distribute the surplus as evenly as possible between each bucket (start at index 0, add 1 to each bucket while subtracting 1 from surplus. If index wraps to end of bucket_size array, start from index 0 again and continue until surplus is 0).

Now that we know the size of each bucket, we can generate the ranges:

for (i=0, k=min; i<number_of_ranges; i++) {
  ranges[i].lo = k;
  ranges[i].hi = k+bucket_sizes[i]-1;
  k += bucket_sizes[i];
}

To find the range of a specific number, simply iterate the ranges array and match the range where ranges[i].lo <= number <= ranges[i].hi.

Here is the full source code that I used to test this out (it's written in C):

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct range
{
    int lo;
    int hi;
};

int generate_ranges(int min, int max, int number_of_ranges, struct range ranges[])
{
    int i;
    int bucket_sizes[number_of_ranges];

    int even_length = (max-min+1)/number_of_ranges;
    for(i=0; i<number_of_ranges; ++i)
        bucket_sizes[i] = even_length;

    /* distribute surplus as evenly as possible across buckets */
    int surplus = (max-min+1)%number_of_ranges;
    for(i=0; surplus>0; --surplus, i=(i+1)%number_of_ranges)
        bucket_sizes[i] += 1; 

    int n=0, k=min;
    for(i=0; i<number_of_ranges && k<=max; ++i, ++n){
        ranges[i].lo=k;
        ranges[i].hi=k+bucket_sizes[i]-1;
        k += bucket_sizes[i];
    }
    return n;
}

int number_range_index(int number, int number_of_ranges, const struct range ranges[]) {
    int i;
    for(i=0; i<number_of_ranges; ++i)
        if(number >= ranges[i].lo && number <= ranges[i].hi)
            return i;
    return number_of_ranges;
}


#define MAX_RANGES 50

int main(int argc, char *argv[]) {
    int i;
    struct range ranges[MAX_RANGES];

    if(argc != 5) {
        printf("usage: %s <min> <max> <number_of_ranges> <number>\n", argv[0]);
        return EXIT_FAILURE;
    }

    int min = atoi(argv[1]);
    int max = atoi(argv[2]);
    int number_of_ranges = atoi(argv[3]);
    int number = atoi(argv[4]);

    assert(max > min);
    assert(number >= min && number <= max);
    assert(number_of_ranges > 0);
    assert(number_of_ranges <= MAX_RANGES);

    printf("min=%d max=%d number_of_ranges=%d number=%d\n\n", min, max, number_of_ranges, number);

    int n = generate_ranges(min, max, number_of_ranges, ranges);
    for(i=0; i<number_of_ranges; i++) {
        if(i<n)
            printf("%s[%d-%d]", i>0?",":"", ranges[i].lo, ranges[i].hi);
        else
            printf("%s[]", i>0?",":"");
    }
    printf("\n\n");

    int number_idx = number_range_index(number, n, ranges);
    printf("method(%d)->[%d,%d]\n", number, ranges[number_idx].lo, ranges[number_idx].hi);

    return EXIT_SUCCESS;
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.