How to create a new random integer between a specif range

Question

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.

justin · Accepted Answer · 2012-11-08 08:12:21Z

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.

edited Nov 8, 2012 at 8:12

answered Nov 8, 2012 at 7:55

justin

105k14 gold badges185 silver badges227 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

RedX Over a year ago

The Fisher-Yeates solution is the way to go here.

spin_eight · Accepted Answer · 2012-11-08 08:55:30Z

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)

answered Nov 8, 2012 at 8:55

spin_eight

4,01511 gold badges42 silver badges67 bronze badges

6 Comments

Benjamin Bannier Over a year ago

See e.g. 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.

spin_eight Over a year ago

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 <stdlib>. Also I have pointed out some disadvantage of rand().

Archie Over a year ago

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

spin_eight Over a year ago

@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?

Archie Over a year ago

@spin_eight See this question on SO: stackoverflow.com/questions/10984974/…

|

Collectives™ on Stack Overflow

How to create a new random integer between a specif range

2 Answers 2

1 Comment

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related