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!

[svero]

Here's code to find a random integer between max and min... So RandomRange(0,5) will return a random number from 0-5 with uniform probability. So you could do...

item = my_items[RandomRange(0,NUM_ITEMS-1)]

And the bonus is that it's a useful general function to add to your stuff.


double RandomProb ()
{
static bSeeded = 0;

if (!bSeeded)
{
srand ((unsigned)time (NULL));
bSeeded = TRUE;
}

double prob = (double)rand () / (double)RAND_MAX;
return prob;
}

INT RandomRange (INT min, INT max)
{
if (max < min)
{
swap (max, min);
}
else if (max == min)
{
return max;
}

//Algorithm requires these asserts
ASSERT (min > INT_MIN / 2);
ASSERT (max < INT_MAX / 2);

//Take NUMBER OF ELEMENTS times random probability.
double dNum = (max - min + 1) * RandomProb ();

//Find largest number that dNum is 'greater than'.
INT range = INT (dNum);

//Unlikey, but can happen that RandomProb returns EXACTLY 1.0000000000000
if (range == max - min + 1)
{
return max;
}

RET_ASSERT (range <= max - min, min);

return min + range;
}

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

[lexaloffle]

I was guessing that cliffski doesn't require the ranges of reals mapping to each integer to be the same size. i.e..

Draw a unit line segment. Draw n evenly spaced points along the line such that the 1st one is at 0 and the nth one is at 1. For any given number (t), find the closest point.

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

This is just patrox's answer with +0.5 to adjust for rounding.

It's n-1 because 11 points will be spaced 0.1 units apart.

This line of code is taken from an animation system were there are n keyframes spread evenly from 0 to 1. When interpolation is turned off, it has to pick the closest frame (i) for a given time (t).

[svero]

This thread is hilarious!

okok guys!...

I think cliffski's learned his lesson and from now on will work out his own algorithms :-)

- S

[Morphecy]

LOL guys :rolleyes: