Algorithm for Random numbers (with certain numbers with higher priority)
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Algorithm for Random numbers (with certain numbers with higher priority)

1. Member
Join Date
Aug 2005
Location
Sweden
Posts
26

## Algorithm for Random numbers (with certain numbers with higher priority)

Simply, what the the title says.

Is there an algorithm for "randomizing a number between A and B and specifying an array of numbers with a priority"

Say I want to develop educational software - for language, etc. So it has 100 words from a list (an array), when you answer wrong the words number in that list gets higher priority and has a more "chance" to come up again and if you answer it wrong when it come again the priority goes even higher, etc.

Therefor making what you know less come up more frequent so you can learn it better.

What I was wondering if there was such an algorithm for this? Or this something that I have to develop on my own - would be great to have a starting point.

2. Senior Member
Join Date
Oct 2008
Posts
1,456

## Re: Algorithm for Random numbers (with certain numbers with higher priority)

in other words, you want to generate pseudo-random numbers following a prescribed probability distribution over a finite set of numbers ...

... now, there are many more or less sophisticated ways of generating random samples, but

in general, you can generate any real random variable R via F^-1(U), where F^-1 is the inverse cumulative distribution function of R and U is the uniform distribution in the real interval [0,1].

this gives also the easiest algorithm for generating pseudo-random numbers following a prescribed probability distribution; for example, if you interpret your array of "priorities" p[j] as the (eventually non-normalized) probability of the "word" w[j] then you have to

1) generate a pseudo-random u in [ 0, p[0] + ... + p[N-1] )
2) traverse p[] until p[0] + ... + p[J] > u for some J
3) w[J] is the wanted pseudo-random sample

of course, the actual algorithm will vary depending on the type of p[] ( you can use integer weights, for example ) or how/when the various quantity are computed/cached/updated ( you can normalize the weights or compute the array of cumulative weights once for all, for example ) ...

3. Elite Member
Join Date
May 2009
Posts
2,413

## Re: Algorithm for Random numbers (with certain numbers with higher priority)

Originally Posted by Deukalion
to have a starting point.
A simple approach is to introduce a drill list of lets say 10 words. To start with you fill it with words randomly selected (*) from the list of 100 words.

Then a word is selected at random from the drill list. If the user fails the word stays in the drill list. If the user succeeds the word is removed from the drill list and replaced with a randomly selected word from the list of 100. Then another word is selected at random from the drill list, etcetera.

It's easy to implement. The drill list doesn't have to hold any words just the index positions of the words in the list of 100.

Although simple I think this approach has a lot of good properties and corresponds fairly well to what you want in a drill learning situation.

(*) In my suggestion random always means drawn with equal probability. If there are 10 words in a list the probability a word gets selected should be 1/10. If there are 100 words the probability for each should be 1/100.
Last edited by nuzzle; September 14th, 2011 at 01:10 AM.

4. ## Re: Algorithm for Random numbers (with certain numbers with higher priority)

Just to add: This site has a related FAQ: http://www.codeguru.com/forum/showthread.php?t=378879. I think the code from the first two posts can be easily adapted to your needs by basically replacing the call to the distribution function with a table lookup.

Also, if you happen to use C++0b, the facilities from the <random> header perhaps are useful. I think particularly the discrete_distribution class looks interesting.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Click Here to Expand Forum to Full Width