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).
3
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]
- Initialize the size of each bucket with the highest evenly possible length:
(max-min+1)/number_of_ranges(integer division) - Then, find the surplus that couldn’t fit evenly in each bucket,
(max-min+1) % number_of_ranges(remainder from integer division) - 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=%dnn", 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("nn");
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;
}
1
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.
5
Here’s a C++11 version of Oskar N’s answer:
/** Divides a given range of values into consecutive sub-ranges as evenly as possible.
* Returns a vector of pairs. The first member of each pair is the min and the second, the max.
*/
std::vector< std::pair<int, int> > generateSubRanges( int mainRangeMin,
int mainRangeMax,
int numberOfSubRanges )
{
std::vector<std::pair<int, int> > result;
std::vector<int> bucket_sizes;
int i;
//init vectors
bucket_sizes.reserve( numberOfSubRanges );
result.reserve( numberOfSubRanges );
for( i = 0; i < numberOfSubRanges; ++i ){
bucket_sizes.push_back( 0 );
result.push_back( {0, 0} );
}
int even_length = (mainRangeMax-mainRangeMin+1)/numberOfSubRanges;
for(i=0; i<numberOfSubRanges; ++i)
bucket_sizes[i] = even_length;
/* distribute surplus as evenly as possible across buckets */
int surplus = (mainRangeMax-mainRangeMin+1)%numberOfSubRanges;
for(i=0; surplus>0; --surplus, i=(i+1)%numberOfSubRanges)
bucket_sizes[i] += 1;
int n=0, k=mainRangeMin;
for(i=0; i<numberOfSubRanges && k<=mainRangeMax; ++i, ++n){
result[i] = { k, k+bucket_sizes[i]-1 };
k += bucket_sizes[i];
}
return result;
}