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

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

  1. #1
    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. #2
    Join Date
    Oct 2008
    Posts
    1,110

    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. #3
    Join Date
    May 2009
    Posts
    2,413

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

    Quote Originally Posted by Deukalion View Post
    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. #4
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,583

    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.
    I was thrown out of college for cheating on the metaphysics exam; I looked into the soul of the boy sitting next to me.

    This is a snakeskin jacket! And for me it's a symbol of my individuality, and my belief... in personal freedom.

Tags for this Thread

Posting Permissions

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


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center