2

I have a range of numbers 1 to 100 which are indices to a list, I need to pick a list at random. If what i am looking for in the list is not found, I need to pick a next random integer within the range which gets me to the list and it should not be the one which was previously selected,, In there a way to do this efficiently in C. I could do it with shuffling an array of indices but I want to know if there is a better way.

To summarize, i need a very good random algorithm which returns an integer which i know is random and was never used before.

I do know about rand(), srand() and randomize(). I am not sure if these serve the purpose.

Nikhil
  • 2,168
  • 6
  • 33
  • 51

2 Answers2

2

arc4random_uniform will do the trick, if available on your system:

uint32_t r = 1U + arc4random_uniform(100); // r = 1...100

If you need a unique number, begin with an array of values and use a Fisher-Yates (aka Knuth) shuffle.

If the array is smaller than the range you could just brute force fill with unique random numbers, then shuffle -- i.e. if you needed only ten numbers, then you could generate it in about 20 random-gen calls. Note that the shuffle would only be needed in this scenario if you also ordered it during population (for faster match lookups).

Another approach would be to populate a vector [1...100] and draw remaining elements from it at random, removing entries as you used them.

justin
  • 104,054
  • 14
  • 179
  • 226
0

you can combine your knowledge of srand, rand and time() with % operation.
% n - gives you reminder from division on n, which is obviously can`t be larger when n.
So in terms of code:

srand(time());
int value = rand() % n; // will give you random values within interval [0,n)

But I need to mention that rand() has some disadvantages, one of them that it is not provide uniform distribution, as probability of lower values are higher (you can find discussion related to this topic on stackoverflow)

spin_eight
  • 3,925
  • 10
  • 39
  • 61
  • 2
    See e.g. http://eternallyconfuzzled.com/arts/jsw_art_rand.aspx why this is usually not a good recommendation, I had to -1 this since you imply you know that your solution is bad but propagate it nevertheless. – Benjamin Bannier Nov 08 '12 at 09:03
  • I don`t agree with you, I advised to use % operation, which can be combined with any technique of random number generation, which ofcourse is not limited to the rand() function provided in . Also I have pointed out some disadvantage of rand(). – spin_eight Nov 08 '12 at 09:09
  • @spin_eight: But you did not mention the real disadvantage of the `%` operator which adds a bias to the results if `n` does not evenly divide `RAND_MAX`. – Archie Nov 08 '12 at 11:42
  • @Archie I am not aware of it, can you give me an explanation on bias which arise in that case or some reference on the source where it is explained? – spin_eight Nov 08 '12 at 12:37
  • 1
    @spin_eight See this question on SO: http://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator – Archie Nov 08 '12 at 12:46
  • Thank you for pointing it out, very helpfull link and explanation. So % operation works only when RAND_MAX < n and in this case it is usless. +1 – spin_eight Nov 08 '12 at 13:02