generate a random number within a range but exclude some in C/C++

Question

Not a new question but its specific to only c/c++ .

For ex- range[1...10] exclude_set [2,5,7,9]

Custom rand function should return remaining numbers with equal probability.

What i have tried is-

1) generate number by rand() %10 function .

2) check if values is present in exclude_Set .if present call rand() again in loop

Interviewer said its brute force approach .I am curious that is there any good algorithm present for c/c++

The question is already answered for Java/C#/PHP on SO

How can I generate a random number within a range but exclude some?

How to get a random value from 1~N but excluding several specific values in PHP?

How to get a random number from a range, excluding some values

PS- I have already tried googling.Even Bing

@πάνταῥεῖ Ok let say in C.I am more concentrated on algorithm. — Ankur, Nov 28 '15 at 14:51
If you're just interested in the algorithm, remove the language tags at all please. — πάντα ῥεῖ, Nov 28 '15 at 14:52
@πάνταῥεῖ Although i have removed c++ tag but i think its bit language specific because in c/c++ there is no support of `nextInt` like in Java/C# — Ankur, Nov 28 '15 at 14:55

Paul Evans · Accepted Answer · 2015-11-28T15:02:43.807

4

A straightforward way is to map the remaining values to an array and use rand() to access them, something like:

int[6] rvec = {1, 3, 4, 6, 8, 10};
// and get numbers with
rvec[rand() % 6];

edited Nov 28 '15 at 15:02

answered Nov 28 '15 at 14:56

Paul Evans

27,315
3
37
54

4

Having all allowed values in a vector/array is quite a wast of space and not acceptable for large sets. Also this will not distribute random values evenly. – too honest for this site Nov 28 '15 at 15:00
@Olaf OP changed to C from C/C++. Edited answer accordingly. – Paul Evans Nov 28 '15 at 15:00

too honest for this site · Answer 2 · 2015-12-16T14:21:50.153

1

For small sets up to e.g. 64 bits, you can use a bitmap with excluded (or included) values:

#define MAX_RANDVAL 10

uint64_t illegal_values = (1ULL<<2) | (1ULL<<5) | ... ;
int rand_val;

do {
    rand_val = rand();
} while ( (rand_val > MAX_RANDVAL) || (illegal_values & (UINT64_C(1) << rand_val) );

However, to get evenly distributed values, you have to loop if an illegal value is encountered.

Enhancements might include exploiting regularities in the sequence. The range may be extended using a hash-algorithm or even a binary search tree. The optimal algorithm heavily depends on the actual requirements. There is no single best algorithm.

edited Dec 16 '15 at 14:21

answered Nov 28 '15 at 15:14

too honest for this site

12,050
4
30
52

The while()-expression is always false, since if rand_val is greater than MAX_RANDVAL, illegal_values & (1ULL << rand_val) will probably not be true at the same time (assuming that no illegal values greater than MAX_RANDVAL are flagged in the bitmask). Did you perhaps mean to use a logical disjunction? – Ctx Dec 16 '15 at 13:30
@Ctx: Thanks , edited. Also corrected a minor flaw with the mask (not critical). – too honest for this site Dec 16 '15 at 14:22

generate a random number within a range but exclude some in C/C++

2 Answers2