Thread: Random Selection - Tabu List

Hey guys,

So my current problem, after great simplifications boils down to this:

Lets say you have a 100 numbers, and I want to pick a random one. If its not 'right' I need to pick another one and continue until a certain success criteria is met (irrelevant what that might be).

My question is how can I fairly efficiently implement it. For example if I'm at a state where I already tried say , 5 and 8. I still have 98 possible numbers to try, but not 5 and 8. How can I accomplish this in c?

[of course I can just always pick a random number 1-100, and keep track of what I already tried, iterate though that list, and if I already tried it, just try picking a new number, however the inefficiency of this will be unacceptable for my needs, I'm afraid. This would only be acceptable (but still ugly) if the success criteria was easy to meet, but would be terribly inefficient when it wouldn't]

Keep an array of 100 numbers 1 to 100.
When you pick a random number, say 5, you grab the number in position [5] (which is 5 initially). To make this number unselectable, just substitute the number in the highest slot (which is 100 now) into it. Decrement "highest" to 99.
Next random choice is limited to 99 positions.
Next time if you happen to choose slot [5] again you'll receive 100 instead.
Each time decrement number of choices of the random generator.

Of course choose indexing 0 to 99 and appropriate numbers and add 1 if you want 1 to 100 range.