gmoque has asked for the wisdom of the Perl Monks concerning the following question:

I have a question about rand() ... I have the following code:

#!/usr/bin/perl my @arr = (); my $counter = 1; for($i=0; $i<32; $i++) { while(1) { $rand = int(rand(32)); # print "testing: $rand\n"; if (grep(/$rand/, @arr) == 0) { print "$counter: $rand\n"; push @arr, $rand; $counter++; last; } } }

The goal is to produce random numbers from 0 to 32, but the sequence has to be without repeating any number, whenever I run this code I always get 23 or 24 numbers, after this the computer keeps generating numbers but I can't make the computer generate the last random numbers.

Any ideas?

I ran the code under Fedora, Cygwin and Active Perl but I get the same behavior on all platforms.

This is the output I get:

$ ./create_random_numbers.pl 1: 29 2: 20 3: 27 4: 31 5: 25 6: 21 7: 19 8: 13 9: 26 10: 12 11: 8 12: 28 13: 11 14: 16 15: 22 16: 17 17: 4 18: 10 19: 23 20: 18 21: 24 22: 15 23: 14 24: 30

After this the scripts "hangs" and the CPU goes to almost 100% usage, I have it running for more that 5 minutes but no luck (I am not expecting to run scripts for more than 5 minutes just to generate random numbers)

Update

Thanks for all the replies what I was looking for is what almut wrote, that little part of the regexp made the difference (/^$rand$/). Although I think the idea of using shuffle is good, I never work with that module before. I think basically now I have my own version of shuffle.

Now my next task will be to test the performance using shuffle and using rand, I will see what is faster.

My final code looks like this:

#!/usr/bin/perl my @arr = (); my $counter = 1; my $range; for($i=0; $i<$range; $i++) { while(1) { $rand = int(rand($range)); if (grep(/^$rand$/, @arr) == 0) { print "$rand\n"; push @arr, $rand; $counter++; last; } } }

Replies are listed 'Best First'.
Re: How much random is rand()?
by merlyn (Sage) on Jan 19, 2009 at 18:17 UTC
    What do you think scalar grep /4/, qw(14) returns?

    Yup. The moment you add 14, you can't ever add 4, because it's a subset of 14. So you get "stuck" adding the last few single-digit numbers, because they're already "within" the longer numbers.

    You should be looking for shuffle instead. Been done quite a few times here already. For the lazy:

    use List::Util qw(shuffle); my @shuffled = shuffle 0..32;
Re: How much random is rand()?
by derby (Abbot) on Jan 19, 2009 at 18:14 UTC

    If I'm reading this correctly, you want the numbers 0-32 in a random order? If so, what you have is not the way to go. What you want to do is shuffle; otherwise, as you've seen, you could go on forever and not complete.

    -derby

    Update: There are some good replies below but I'm I the only one having a problem with

    while(1) { $rand = int(rand(32)); ... }
    while the comments about 4 never getting into the list if 14 is all ready in the list are valid ... there's also the quite real possiblity of 4 never being returned from rand! Or at the very least you may get a large number of duplicate 14s before you ever get the chance to grep (validly) for 4. Shuffling is definitely what you want if what you want is 0-32 in a random order.

      ... there's also the quite real possiblity of 4 never being returned from rand!

      In that case, the pseudo random number generator would be broken (taking 'never' literally). In theory, it might occasionally take a 'long time' for any certain number to occur, but that's unlikely in practice.

      Actually, presuming a statistically equal distribution of values returned by the PRNG, the probability to get a certain (integer) number is expected to be 1/N (N being 32 in this case).  So, even on the last turn, when all but one of the 32 values are already taken, the chance to get the final remaining number is 1/32 (or 32 attempts, on average); when there are still two numbers left, the chance is 2/32 (16 attempts), etc.

      Doing some simple simulation statistics confirms this quite well (although slightly modified in implementation, the central algorithm is functionally the same as that of the OP):

      #!/usr/bin/perl use strict; use warnings; my $n = 1e4; # number of runs for the statistics my $N = 32; my @sum; my @max = (0)x($N+1); for (1..$n) { my @have_num = (); for my $i (1..$N) { my $attempts = 0; while(1) { my $rand = int(rand($N)); #print "."; $attempts++; unless ($have_num[$rand]) { #print " $i: $rand\n"; $have_num[$rand] = 1; last; } } $sum[$i] += $attempts; $max[$i] = $attempts if $attempts > $max[$i]; } } for my $i (1..$N) { my $avg = $sum[$i]/$n; my $bar = "*" x int($avg+0.5); printf "%2d: %6.3f [%6.3f] %s max=%d\n", $i, $avg, $N/($N-$i+1), $bar, $max[$i]; } __END__ 1: 1.000 [ 1.000] * max=1 2: 1.033 [ 1.032] * max=4 3: 1.065 [ 1.067] * max=4 4: 1.104 [ 1.103] * max=5 5: 1.142 [ 1.143] * max=7 6: 1.186 [ 1.185] * max=7 7: 1.230 [ 1.231] * max=8 8: 1.283 [ 1.280] * max=8 9: 1.334 [ 1.333] * max=8 10: 1.392 [ 1.391] * max=10 11: 1.453 [ 1.455] * max=10 12: 1.521 [ 1.524] ** max=11 13: 1.601 [ 1.600] ** max=13 14: 1.684 [ 1.684] ** max=13 15: 1.779 [ 1.778] ** max=14 16: 1.882 [ 1.882] ** max=16 17: 1.999 [ 2.000] ** max=19 18: 2.137 [ 2.133] ** max=17 19: 2.283 [ 2.286] ** max=23 20: 2.462 [ 2.462] ** max=20 21: 2.674 [ 2.667] *** max=26 22: 2.904 [ 2.909] *** max=29 23: 3.198 [ 3.200] *** max=31 24: 3.551 [ 3.556] **** max=37 25: 3.996 [ 4.000] **** max=48 26: 4.554 [ 4.571] ***** max=47 27: 5.331 [ 5.333] ***** max=55 28: 6.400 [ 6.400] ****** max=79 29: 8.026 [ 8.000] ******** max=95 30: 10.597 [10.667] *********** max=140 31: 15.983 [16.000] **************** max=211 32: 32.092 [32.000] ******************************** max=343

      The second column is the number of attempts, averaged over 10000 runs in this case (a single run doing what the OP's code did). The values in brackets are the corresponding expected values. "max=" is the worst case number of attempts that ever occurred.

      $rand = int(rand(32));
      That'll never return 32.

      rand says:

      Returns a random fractional number greater than or equal to 0 and less than the value of EXPR.
      For random integers between 0 and 32 use int rand 33

      BUT, as others have suggested, shuffle is the way to go

Re: How much random is rand()?
by kyle (Abbot) on Jan 19, 2009 at 18:15 UTC

    Use List::Util.

    use List::Util qw( shuffle ); my @arr = shuffle 0 .. 32; print join q{, }, @arr; print "\n"; __END__ 15, 27, 5, 11, 24, 19, 32, 13, 20, 17, 21, 16, 7, 0, 1, 26, 18, 6, 4, +2, 10, 30, 29, 31, 23, 25, 12, 3, 8, 9, 28, 22, 14
Re: How much random is rand()?
by almut (Canon) on Jan 19, 2009 at 18:15 UTC

    It's your grep /$rand/ ... Try /^$rand$/, or $_ eq $rand :)

Re: How much random is rand()?
by setebos (Beadle) on Jan 19, 2009 at 20:07 UTC
      That wasn't the question, and your claim doesn't have to be true. perl (lowercase) doesn't have its own random number generator. When Perl is build, it probes the OS to see what random number generators its C library has available. It picks what it thinks is best.

      But if all your OS has to offer is a 16-bit random number generator, you're not at all better off than in PHP. Perl is fully at the mercy of the OS; while the article you point at seems to state PHP programmers have the option of using either a function from the OS, or a PHP supplied one.

      BTW, your href is broken.