Thread: Random Numbers

  1. #1
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342

    Unhappy Random Numbers

    hi all,
    I am required to generate an array having 100 random numbers, where there is absolutely no repetition and the case where the ith element of the array is not the number " i " itself is not allowed ..
    I found some ideas where we could generate pseudo random numbers using the idea:
    x(n+1) = (x(n)*P1 + P2) (mod N) .
    where x(n) is the nth element,
    P1 and P2 are constants
    N is also a constant.. the value of x0 must be chosen appropriately..
    This does not guarantee absolute randomness..
    Can some one help me with this please...

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    I would just use something simple like rand() to generate the random numbers. Then just check if the number is already in the array and that it's not the same as the array index you're storing it in. If one of those checks fails just grab another random number and try again.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    int main(void)
    {
      int nums[100];
      int i, j;
      int again;
    
      srand(time(0));  // Seed pseudo random number generator
    
      for(i = 0;i < 100;++i)
      {
        do
        {
          again = 0;
    
          nums[i] = rand();
    
          if(nums[i] == i)
          {
            again = 1;
            continue;
          }
    
          for(j = 0;j < i;++j)
            if(nums[j] == nums[i])
            {
              again = 1;
              break;
            }
        } while(again);
      }
    
      for(i = 0;i < 100;++i)
        printf("nums[%d] = %d\n", i, nums[i]);
    
      return 0;
    }
    Last edited by itsme86; 06-09-2006 at 11:30 AM.
    If you understand what you're doing, you're not learning anything.

  3. #3
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Since rand() returns a number from 0 to RAND_MAX (which is <= INT_MAX, and is on two of my compilers, 2^16-1 and 2^32-1), it might take a long time to get the value you're looking for. You should limit the value (but not with modulus): http://eternallyconfuzzled.com/articles/rand.html.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  4. #4
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    I didn't see in his post that he was looking for specific values. Since the only qualification is that none of the numbers can match (or equal the array index) then I think the largest range possible would be best.
    If you understand what you're doing, you're not learning anything.

  5. #5
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    rand() does not guarantee absolute randomness either. It uses a simple linear congruential algorithm. Go use some radioactive kitten litter for some real random values.

    You could use a primitive root modulo a prime to loop through a set of distinct values. Repetitions are mathematically impossible. Or set the array values using indexes from a randomly generated hash table.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  6. #6
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Linux also provides /dev/random and /dev/urandom. It uses random events such as keyboard strokes and harddrive activity to generate entropy data which you can use for more-than-pseudo-random-numbers if you really need that (and your OS supports it).

    http://www.die.net/doc/linux/man/man4/random.4.html
    Last edited by itsme86; 06-12-2006 at 10:25 AM.
    If you understand what you're doing, you're not learning anything.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > I am required to generate an array having 100 random numbers, where there is absolutely
    > no repetition and the case where the ith element of the array is not the number " i " itself is
    > not allowed ..
    This hardly describes any definition of random.

    This seems to fit your rules, but is decidedly non-random
    Code:
    for ( i = 0 ; i < 100 ; i++ ) arr[i] = i + 1;
    No repetition, and no arr[i] contains i

    Perhaps you need to say why you need an array which matches these properties you list.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    This hardly describes any definition of random.
    To be fair, the requirements on no repetition and "ith element of the array is not the number " i " itself" can be seen as additional requirements on top on the 'randomness'.
    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. #9
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342

    clarification

    hi,
    Apparently, the problem was not very clear.
    I wish to state the problem again:

    "I want an array of size 100 filled with random numbers.
    The range of numbers is between 0 and 99.
    On top of this, there should not be any repeated numbers and
    the number in the ith position of the array must not be the number "i" itself." I am sorry for the trouble, if any.
    No genuine requirement as such, this problem came up when a bunch of us were discussing random numbers in general
    thanks,

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Fill the array from 0 to 99.
    Shuffle it as long as there are any elements whose value matches its index.


    Quzah.
    Hope is the first step on the road to disappointment.

  11. #11
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Shuffle it as long as there are any elements whose value matches its index.
    What if the process never completes? It might happen. In any case, that is a helluva inefficient operation, in theory.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Well, after shuffling check for elements whose value matches the index. Shuffle those elements, or simply swap them around.
    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

  13. #13
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by jafet
    What if the process never completes? It might happen. In any case, that is a helluva inefficient operation, in theory.
    Maybe the way you write it makes it inefficient. It depends on how you shuffle. Then again, I don't shuffle like a moron.

    Besides, the OP said nothing of efficiency.


    Quzah.
    Last edited by quzah; 06-13-2006 at 04:11 AM. Reason: Add comment regarding efficiency.
    Hope is the first step on the road to disappointment.

  14. #14
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    Quote Originally Posted by ME
    in theory
    Anyway, random_shuffle is a quick fix for the OP's problem, and should work in most* practical situations.

    * "most" == "inconcievably huge proportion of".

    I should stop thinking like a math geek
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Anyway, random_shuffle is a quick fix for the OP's problem,
    I agree, though there's still the check for elements whose value matches the index. I dont think std::random_shuffle has any guarantees on that.

    and should work in most* practical situations.
    * "most" == "inconcievably huge proportion of".
    Unfortunately, this is the C forum, so a #include <algorithm> followed by the use of std::random_shuffle may not be practical.
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. questions....so many questions about random numbers....
    By face_master in forum C++ Programming
    Replies: 2
    Last Post: 07-30-2009, 08:47 AM
  2. Doubts regarding random numbers generation
    By girish1026 in forum C Programming
    Replies: 9
    Last Post: 12-31-2008, 10:47 PM
  3. random numbers limit
    By HAssan in forum C Programming
    Replies: 9
    Last Post: 12-06-2005, 07:51 PM
  4. Generate random numbers in Lucky7 project using C#
    By Grayson_Peddie in forum C# Programming
    Replies: 1
    Last Post: 04-11-2003, 11:03 PM
  5. random numbers
    By lil_plukyduck in forum C++ Programming
    Replies: 5
    Last Post: 01-14-2003, 10:14 PM