Thread: Random Number

  1. #31
    Cereal Killer
    Join Date
    Jun 2004
    Posts
    8

    More randomness

    Hi, sorry if I'm asking a dumb question (having looked through the FAQ/boards etc), but here goes:

    I need to generate a list of numbers from 1 (to a set number, for e.g. 25) in a random order. However, I can't have the same number twice, but I need the list ordering to be random.

    ANy thoughts?

  2. #32
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Have an array that will store the numbers, a variable that will tell you how many items are in the array, and a temporary variable that will hold the result of each random call.

    Process would be:
    1) call the random generator and put value into the temporary variable
    2) Search the array (using the above mentioned variable to make sure you only look at values you've put in already).
    3) If you didn't find a match, add in the temp and increase the size counter. Repeat until filled

  3. #33
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Quote Originally Posted by Thantos
    Have an array that will store the numbers, a variable that will tell you how many items are in the array, and a temporary variable that will hold the result of each random call.

    Process would be:
    1) call the random generator and put value into the temporary variable
    2) Search the array (using the above mentioned variable to make sure you only look at values you've put in already).
    3) If you didn't find a match, add in the temp and increase the size counter. Repeat until filled
    Search an array for each new random number? Even not taking into account duplicate values, this is a terribly inefficient process. IMO it's much better to just fill an array with the range of values and permute it randomly:
    Code:
    #include <algorithm>
    #include <cstdlib>
    #include <iostream>
    
    using namespace std;
    
    double random();
    
    int
    main()
    {
      int *vals;
      int  n;
    
      cout<<"Upper limit: ";
      if (!(cin>> n)) {
        cerr<<"Input error"<<endl;
        exit(EXIT_FAILURE);
      }
      // Make and fill array
      vals = new int[n];
      for (int i = 0; i < n; i++) {
        vals[i] = i + 1;
      }
      // Random permutation
      for (int i = 0; i < n - 1; i++) {
        int x = static_cast<int>(random() * (n - i));
        swap(vals[i], vals[i + x]);
      }
      // Prove that it works and clean up
      for (int i = 0; i < n; i++) {
        cout<< vals[i] <<endl;
      }
      delete [] vals;
    }
    
    double
    random()
    {
      return static_cast<double>(std::rand()) / RAND_MAX;
    }
    My best code is written with the delete key.

  4. #34
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    But what if you only wanted 20 numbers with a max value of 10000?

    And I wasn't going for efficiently but ease of use and understanding for the questioner

  5. #35
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >But what if you only wanted 20 numbers with a max value of 10000?
    Then I would use a more suitable data structure than a simple array. But that wasn't the question. The question was a list of numbers from 1 to N in random order.
    I need to generate a list of numbers from 1 (to a set number, for e.g. 25) in a random order.
    >And I wasn't going for efficiently but ease of use and understanding for the questioner
    I know, but I can't resist giving you a hard time every now and then. It keeps you on your toes.
    My best code is written with the delete key.

  6. #36
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I'm not sure why Preludes indicates that rand()/RAND_MAX is less likely to give a string of equal values on repeated values than rand()/modulus
    Using the low order bits of a random number may not result in a good distribution. I've seen long strings of repeating numbers when using modulus with rand.
    From what I see, Prelude is not talking about repeating values, but about the random distribution.
    Her argument is that dividing by RAND_MAX conserves this distribution, while the modulo method often does not.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #37
    jasondoucette.com JasonD's Avatar
    Join Date
    Mar 2003
    Posts
    278
    Quote Originally Posted by weirdbeardmt
    I need to generate a list of numbers from 1 (to a set number, for e.g. 25) in a random order. However, I can't have the same number twice, but I need the list ordering to be random.
    The easiest way is this:

    1. create the list storing 1..25, in order, in the indices 0..24
    2. loop through the indicies, i = 0..24, pick a random index, j = 0..24, and swap the two.

    This way, you swap a random index with each position, assuring that each index is swapped out at least once.

  8. #38
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    hmm... I did not see before posting that this thread was already several pages in length.
    Anyway...

    Any deterministic random number generator is predictable, i.e. rand().
    Well, they are deterministic

    There are devices which you can plug into your computer in order to generate non-deterministic random numbers.
    Incidentally, Hotbits at fourmilab.ch provides such a generator, online.

    For a pseudo-random number generator, I tend to use the Mersenne Twister, with a particular C++ implementation by Rick Wagner.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #39
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    The problem with rand()%n using only the lower order bits is only a problem when n is a power of two.
    Thus, the problem with rand()%n is not that much of a problem.

    If you write rand()%3, the higher-order bits should also be taken into consideration.

    Am I not correct, Prelude?

    There are devices which you can plug into your computer in order to generate non-deterministic random numbers.
    I have made an encryption program that uses noise from the microphone compressed with MD5 to generate keys of many megabits.
    http://www.strandmark.com/otp.shtml
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  10. #40
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    The problem with rand()%n using only the lower order bits is only a problem when n is a power of two.
    Thus, the problem with rand()%n is not that much of a problem.

    If you write rand()%3, the higher-order bits should also be taken into consideration.
    I think that this is still a problem, since they arent always "taken into consideration" evenly.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #41
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Am I not correct, Prelude?
    Yes, the problem is most obvious when N is a power of 2.
    My best code is written with the delete key.

  12. #42
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Bah must have misread the question

    I know, but I can't resist giving you a hard time every now and then. It keeps you on your toes
    Sure pick an easy target (large feet)

  13. #43
    Cereal Killer
    Join Date
    Jun 2004
    Posts
    8
    What do you guys make of these nag routines which my dept. provides as a default install?

    http://www.iss.soton.ac.uk/manuals/a...c/summary.html (about half way down for Random Number generators). I've used the equivalent in Fortran, but never in C...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. rapid random number generation problem
    By Newton in forum C Programming
    Replies: 17
    Last Post: 09-19-2008, 02:08 PM
  2. Random number in range generation.
    By hebali in forum C Programming
    Replies: 19
    Last Post: 03-04-2008, 10:46 AM
  3. adding a number to a number
    By bigmac(rexdale) in forum C Programming
    Replies: 11
    Last Post: 10-24-2007, 12:56 PM
  4. random number tutorial
    By 7stud in forum C++ Programming
    Replies: 3
    Last Post: 07-26-2005, 02:41 PM
  5. Random Number Generator
    By Ikurik in forum C++ Programming
    Replies: 16
    Last Post: 08-17-2003, 07:34 PM