CODEWITHSUNDEEP
c++crandom
atoMerz
atoMerz

Reputation: 7672

Unbalanced random number generator

I have to pick an element from an ascending array. Smaller elements are considered better. So if I pick an element from the beginning of the array it's considered a better choice. But at the same time I don't want the choice to be deterministic and always the same element. So I'm looking for

a random numbers generator that produces numbers in range [0, n], but the smaller the number is, the more chance of it being produced.

This came to my mind: 

num = n;
while(/*the more iteration the more chance for smaller numbers*/)
  num = rand()%num;

I was wondering if anyone had a better solution.
I did look at some similar questions but they have details about random number generation generally. I'm looking for a solution to this specific type of random number generation, either an algorithm or a library that provides it.

Upvotes: 3

Views: 770

Answers (4)

Mark Essel
Mark Essel

Reputation: 4646

Two tools will solve many random distribution needs

1) A uniform random number generator which you have

2) and a function which maps uniform values onto your target distribution

I've gotta head to the city now, but I'll make note to write up a couple of examples with a drawing when I get back.

There are some worthwhile methods and ideas discussed in this related question (more about generating a normal pseudo random number)

Upvotes: 1

thiton
thiton

Reputation: 36059

Use an appropriate random distribution, e.g. the rounded results of an exponential distribution. Pick a distribution that fits your needs, document the distribution you used, and find a nice implementation. If code under the GNU Public License is an option, use the excellent GNU Scientific Library (GSL), or try Boost.Random.

Upvotes: 1

vidit
vidit

Reputation: 6461

Generate a Random number, say x, between [0,n) and then generate another Random floating point number, say y, between [0,1]. Then raise x to the power of y and use floor function, you'll get your number.

int cust(int n)
{
  int x;
  double y, temp;
  x = rand() % n;
  y = (double)rand()/(double)RAND_MAX;
  temp = pow((double) x, y);
  temp = floor(temp);
  return (int)temp;
}

Update: Here are some sample results of calling the above function 10 times, with n = 10, 20 and 30.

2 5 1 0 1 0 1 4 1 0

1 2 4 1 1 2 3 5 17 6

1 19 2 1 2 20 5 1 6 6

Upvotes: 3

default locale
default locale

Reputation: 13456

Simple ad-hoc approach that came to my mind is to use standard random generators, but duplicate indices. So in the array: 

0, 0, 0, 1, 1, 2, 3

odds are good that smaller element will be taken.
I dont' know exactly what do you need. You can also define your own distribution or maybe use some random number generation libraries. But suggested approach is simple and easy to configure.
UPDATE2: You don't have to generate array explicitly. For array of size 1000, you can generate random number from interval: [0,1000000] and then configure your own distribution of selected values: say, intervals of length 1200 for smaller values (0-500) and intervals of length 800 for larger (500-1000). The main point that this way you can easily configure the probability and you don't have to re-implement random number generator.

Upvotes: 3

Related Questions