Help me with this silly algorithm...

[cliffski]

I know it should be easy but im getting old...

Say i have a variable number of objects (at least 1)
and a float value from zero to one

I need to select the object that is the closest match to the float.
so if i have 5 objects and the value is 0.5 I want the 3rd object.
if the value is 0 i want the first object (object 0). if its 1.0f i want the 5th object (object 4)

This needs to work for every value from 0 to 1.

I bet this can be done in 1 line of C++, I just cant concentrate
Its not good enough to just cast an int, I need it to be the closest match without rounding in an arbitrary direction.
Cheers!

[patrox]

probably:

long indexOfObject = (long)(thefloat*(float)(maxObjects-1)) ;

pat.

[cliffski]

doesn't that cast down though? so 0.49 is considered 4 when there are 10?

[Nikster]

you don't need the -1 as if you have 10 objects 1.0 would = 9

[Jim Buck]

Actually, if you want each object to have equal chance of getting picked, you have to "partition" 1.0 into slices of maxObjects. (Otherwise, if you just do simple rounding, the first and last object will have half the chance that the others will.) So:

// this will assume you want zero-based indexing
long indexOfObject = (long)(thefloat*(float)maxObjects);
if(indexOfObject == maxObjects)indexOfObject--;

The above gives every single index equal chance of being chosen *except* for the last value. It will have one more float value that can choose it: 1.0.

As an example, consider the above code on maxObjects of 4:
.00 - .24999 ----> 0
.25 - .49999 ----> 1
.50 - .74999 ----> 2
.75 - .99999 ----> 3
1.0 -------------> 3 (the is because of the if-statement and the reason why the last value will have one more float value that can choose it)

[Nemesis]

Indeed, the solution works for the range 0.0 - 1.0 inclusive, except for 1.0 itself which should be treated as an exception. A simple if/then or wrapping the expression in a max(...) function should do.

I'm not surprised at all you got stuck on this.. I can often handle complex stuff but am befuddled by the simplest ones.. duh!

[lexaloffle]

Right. Now we have everything we need to derive a correct answer.

1. patrox: i = t*(n-1)
2. cliffski: i > t*(n-1)
3. Nikster: i = t*n
4. Jim: i = (t==1) ? n-1 : t*n
5. Svero: rand()%n ^_^

If we assume [1] to be correct, then [3] must be false, because (n-1) is clearly not equal to n. However, [3] can't be false because it is usually not the same result as [5], and svero is usually right. Therefore, [1] is false. This means that [2] must be true, because if i != x, then i >x, unless i < x which would be ridiculous. So i == x+y (where x == t*(n-1) and y is a positive number), but we still do not know the value of y. We can see by [4] that it is sometimes 0 and somtimes 1. Therefore, on average it is 0.5, which gives us the following result:

i = t*(n-1)+0.5

And with casting:


i = (int)(t*(float)(n-1)+0.5);


_

[Jim Buck]

That's not right. For example, in the case of 4 objects, you want 0 - .24999 to map to 0. In your case .24999 becomes 1.24997 (3.0 * .24999 + 0.5).. and when cast as an int becomes 1... not 0 like it should. Any formula that is different from t*n will inherently not give equal chance to all the possible index values.

[cliffski]

my head hurts

[grimreaper]

Those who dont read "Numerical Recipes in C" are condemned to fsck up...

Dont be tempted to use the following; it uses the low order bytes which dont have enough entropy.

// returns a random integer in the range 1 to maxObjects.
int ClifskisNotVeryRandyNumber( unsigned int maxObjects )
{
return 1+( rand() % maxObjects );
}

Instead use:

// returns a random integer in the range 1 to maxObjects.
int ClifskisRandyNumber( unsigned int maxObjects )
{
return 1+(int) ( maxObjects*rand()/(RAND_MAX+1.0) );
}

// returns a random integer in the range minRange to maxRange.
int ClifskisRandyNumber( unsigned int rangeMin, unsigned int rangeMax )
{
return rangeMin+(int) ( rangeMax*rand()/(RAND_MAX+1.0) );
}

Dont forget to initialize srand somewhere.

BTW, random number generation is much harder than it looks.

grimreaper

PS
Hey Svero: you had to special case RandomProb returning exactly 1 coz you didnt add 1 to RAND_MAX.

[svero]

Hey Svero: you had to special case RandomProb returning exactly 1 coz you didnt add 1 to RAND_MAX.

I guess that's a good trick ... and yet.. 1.0 is a valid probability. Course I suppose there's no particular use for returning a probablity of 1 vs .999999999... in general as it rarely even comes up.