random pair generator

[noyk]

Hi!

i need to generate a pair of random numbers between 0 to 100
e.g. 0 - 2, 5 - 54, 98 - 100
there is two conditions, (1) the same number is not used as a pair e.g. 1-1, 2-2
(2) the same pair of number is not repeated and that would include 1-2, 2-1
the first condition is pretty easy, just that i could not find any way to account for the second?


for ($x=1 ; $x < 10; $x++)
{
&rand_num;
}

sub rand_num
{
my $range = 100;
$i = int(rand($range));
$j = int(rand($range));
if ($i==$j)

{
&rand_num;
}

 

[feherke]

Hi

Probably is not the best, but I would go with this :

@uniqpair=();
for ($x=1;$x<10;$x++) {
  &rand_num;
}

sub rand_num
{
  my $range = 100;
  $i = int(rand($range));
  $j = int(rand($range));
  return &rand_num if $i==$j;

  $ok=1;
  foreach $one (@uniqpair) {
    if ($i==${$one}[0] || $j==${$one}[0] || $i==${$one}[1] || $j==${$one}[1]) {
      $ok=0;
      last;
    }
  }
  return &rand_num unless $ok;

  push @uniqpair,[($i,$j)];
  return ($i,$j);
}

Note, that I kept the recursive call just because you used it, but in this case I would not use it otherwise.

Feherke.

http://rootshell.be/~feherke/

 

[KevinADC]

This is adapted from a random number generating function I wrote. Its probably a bit of overkill for just two number sequences as it was written to generate longer strings of random/unique sets.

use strict;
use warnings;
 
my $length = 2; # the amount of numbers per string
my $max = 20; # the number of strings
my @strings; # array to store the strings
for (1..$max) {
   push @strings, rand_nums($length);
}
print "$_\n" for @strings;
{
   my %cache; # create a "static" variable
   sub rand_nums {
      my $num;
      my %local_cache; # create a new hash
      my ($length) = @_; # the length of the random number string passed to the sub
      my $serial = int(rand(100))+1; # get the first number for the serialized string
      $local_cache{$serial} = 1; # store the first number in the hash
      for (2..$length) {# start at 2 because we already have the first number
         $num = int(rand(100))+1; # get a new random number
         redo if exists $local_cache{$num}; # redo the loop if the number already exists
         $local_cache{$num} = 1; # store the number in the hash
         $serial .= "-$num"; # append to the serialized string
      }
      rand_nums($length) if exists $cache{$serial}; # redo the function if the key already exists
      rand_nums($length) if exists $cache{"$num-$serial"}; # redo the function if the key already exists
      $cache{$serial}=1; # store the new key in the hash (%cache)
      return $serial;
   }
}

------------------------------------------
- Kevin, perl coder unexceptional!

 

[KevinADC]

Here is is a little simplified for your specific requirments:

use strict;
use warnings;
 
my $max = 20; # the number of strings
my @strings; # array to store the strings
for (1..$max) {
   push @strings, rand_nums();
}
print "$_\n" for @strings;
{
   my %cache; # create a "static" variable
   sub rand_nums {
      my $first_num = int(rand(100))+1;
      my $second_num = int(rand(100))+1;
      my $first_str = "$first_num-$second_num";
      my $second_str = "$first_num-$second_num";
      rand_nums() if exists $cache{$first_str}; # redo the function if the key already exists
      rand_nums() if exists $cache{$second_str}; # redo the function if the key already exists
      $cache{$first_str}=1; # store the new key in the hash (%cache)
      $cache{$second_str}=1; # store the new key in the hash (%cache)
      return $first_str;
   }
}

------------------------------------------
- Kevin, perl coder unexceptional!

 

[KevinADC]

oops..... needed to add aline so you don;t get a string like 10-10

use strict;
use warnings;
 
my $max = 20; # the number of strings
my @strings; # array to store the strings
for (1..$max) {
   push @strings, rand_nums();
}
print "$_\n" for @strings;
{
   my %cache; # create a "static" variable
   sub rand_nums {
      my $first_num = int(rand(100))+1;
      my $second_num = int(rand(100))+1;
      [b]rand_nums() if ($first_num == $second_num);[/b]
      my $first_str = "$first_num-$second_num";
      my $second_str = "$first_num-$second_num";
      rand_nums() if exists $cache{$first_str}; # redo the function if the key already exists
      rand_nums() if exists $cache{$second_str}; # redo the function if the key already exists
      $cache{$first_str}=1; # store the new key in the hash (%cache)
      $cache{$second_str}=1; # store the new key in the hash (%cache)
      return $first_str;
   }
}

------------------------------------------
- Kevin, perl coder unexceptional!

 

[noyk]

thanks, not exactly what i want, but i get the idea

it is more like this

foreach $one (@uniqpair)
{
if ($i==${$one}[0] && $j==${$one}[1] || $j==${$one}[0] && $i==${$one}[1] )
{
$ok=0;
last;
}
}

Kevin, somehow your codes do not seems to satisfy either conditions at all..

i change

my $second_str = "$first_num-$second_num";

to

my $second_str = "$second_num-$first_num";

but it still doesnt work out

 

[prex1]

Kevin's 2nd version works for me (didn't test the first one).
Anyway here is another version, better tuned to the goal and possibly faster. I chose to return ordered pairs, as I find this to be neater, because you don't want inverted equal pairs.

use strict;
use warnings;
for(my$i=0;$i<10;$i++){print rand_pair(),"\n"}
{
  my%cache;
  sub rand_pair{
    use constant MAXNUM=>100;
    die"Reached maximum number of pairs!\n"if keys%cache>=MAXNUM*(MAXNUM-1)/2;
    my($num1,$num2);
    while(1){
      $num1=int(rand(MAXNUM))+1;
      $num2=int(rand(MAXNUM))+1;
      if($num2<$num1){
        $cache{$num2-$num1}=1,return"$num2-$num1"unless exists$cache{$num2-$num1};
      }elsif($num1<$num2){
        $cache{$num1-$num2}=1,return"$num1-$num2"unless exists$cache{$num1-$num2};
      }
    }
  }
}

The [tt]die[/tt] addresses a condition that could lead to an infinite loop. However, if the number of pairs sought is small (<100), that condition may be removed and the line [tt]$num1=int(rand(MAXNUM))+1;[/tt] may go before the [tt]while[/tt]: the code will execute slightly faster (but of course if you require a number of pairs close to the maximum 4950, the code could become quite slow).

Franco

http://www.xcalcs.com

: Online engineering calculations

http://www.megamag.it

: Magnetic brakes for fun rides

http://www.levitans.com

: Air bearing pads

 

[KevinADC]

oops.... this line:

my $second_str = "$first_num-$second_num";

should be:

my $second_str = "$second_num-$first_num";

My code seems to work fine (after the change above), not sure why it is not working for you. Did you change something? Here's the output running it with 20 as the number of strings to return:

40-28
96-73
22-16
11-30
9-76
85-11
79-61
36-59
53-9
98-95
59-17
98-38
84-38
70-31
11-40
16-22
82-79
77-15
71-38
31-26

here's the output of Francos code, notice the difference?

13-94
57-69
12-57
18-45
64-88
27-100
17-34
35-38
14-22
9-65
42-71
50-97
21-31
53-95
51-88
12-79
2-94
2-78
38-51
41-92

With Francos code the first number in the pairs is always lower than the second number. Maybe that is not important though.


------------------------------------------
- Kevin, perl coder unexceptional!

 

[noyk]

yes, i made some changes at

my $max = 10;

and

my $first_num = int(rand(10))+1;
my $second_num = int(rand(10))+1;

so that I can make sure that both conditions are met at a smaller number sets

i get this results

7-7 <--
10-6
1-3
8-6
2-7
2-3
7-9
3-9
2-6
10-1

repeat again,

4-8
5-3
8-3
10-1
10-2 <--
6-9
8-6
8-10
4-3
10-2 <--

franco's seems to work fine, although it tend to stop midway when i made similar changes like this

use constant MAXNUM=>10;

and yes, the order(lower or higher) of the first and second number does not matter to me..

 

[KevinADC]

OK, I see the problem. This looks like it works OK now:

use strict;
use warnings;
 
my $max = 10; # the number of strings
my @strings; # array to store the strings
for (1..$max) {
   push @strings, rand_nums();
}
print "$_\n" for @strings;
{
   my %cache; # create a "static" variable
   sub rand_nums {
      my $first_num = int(rand(10))+1;
      my $second_num = int(rand(10))+1;
      while ($first_num == $second_num) {
         $second_num = int(rand(10))+1;
      }
      my $first_str = "$first_num-$second_num";
      my $second_str = "$second_num-$first_num";
      rand_nums() if exists $cache{$first_str}; # redo the function if the key already exists
      rand_nums() if exists $cache{$second_str}; # redo the function if the key already exists
      $cache{$first_str}=1; # store the new key in the hash (%cache)
      $cache{$second_str}=1; # store the new key in the hash (%cache)
      return $first_str;
   }
}

Note that I have not included any checking to make sure you don't do something to put the code into an infinite loop. That could happen if you use to low a range of numbers to try and return too many sets of numbers. Franco did write something into his code to avoid that but I don't see the need as long as you understand why the code would go "loopy".

------------------------------------------
- Kevin, perl coder unexceptional!

 

[prex1]

er...The following lines should be revised as follows (this is my bad attitude of writing concise code ):

      if($num2<$num1){
        $cache{"$num2-$num1"}=1,return"$num2-$num1"unless exists$cache{"$num2-$num1"};
      }elsif($num1<$num2){
        $cache{"$num1-$num2"}=1,return"$num1-$num2"unless exists$cache{"$num1-$num2"};
      }

However I wonder what are you doing with those 'random' pairs, as they aren't really random.
To see what I mean, suppose you use the numbers 1-10 and you have already output 44 pairs: the next pair is not random in any way, as there is only one left pair to output. And if you have already 43, there are only two possibilities to choose from, and so on.
In fact, when you expect a random element from a set with a fixed number of elements (like a set of integers, not like a set of reals, where the number is also finite but very large), if you don't allow for repetitions, your random elements will inevitably become less and less random as you go on.

Franco

http://www.xcalcs.com

: Online engineering calculations

http://www.megamag.it

: Magnetic brakes for fun rides

http://www.levitans.com

: Air bearing pads

 

[prex1]

Kevin, your code made me think about recursion, so I would like to comment a bit on it.
My first point is that a recursive sub must privately own all of its variables, otherwise unpredictable results will be assured. In your code there is one common variable ([tt]%cache[/tt]), and the result is that every call to [tt]rand_nums[/tt] will add keys to it, independently of this call being successful or not.
Now when you find a pair that's in [tt]%cache[/tt] , you call again [tt]rand_nums[/tt] with the only outcome that more pairs will be added to [tt]%cache[/tt] without using them, as the result of the call cannot be used as it is not returned. You return instead the original duplicated pair, and in fact your code produces duplicate pairs. Also it generates a perl error that I've never met before: Deep recursion on subroutine "main::rand_nums" at... : this is because so many unused pairs may be added to [tt]%cache[/tt] that none are left.
My conclusion is that recursive routines are dangerous and should not be used for situations where a loop will do. The preferred usage of recursion should be for cases where the domain of the routine becomes smaller at every call, so that it will necessarily get at a minimum value, where the recursion will be stopped. An example may be the calculation of the determinant of a matrix, that is based on the determinants of matrices of order-1, and so on, till the order 1 is reached and the single value left is simply returned, without calling again the function.
Thanks to you for making me think over this problem, I've learned something.

Franco

http://www.xcalcs.com

: Online engineering calculations

http://www.megamag.it

: Magnetic brakes for fun rides

http://www.levitans.com

: Air bearing pads

 

[KevinADC]

It is possible to get the deep recursion warnings with the code I posted. I would not use something like that for anything that could get out of control or cause too much recursion. In this case the only problem is if the person tries to return too many results from too small a pool of possible results. Perl defines the deep recursion break point as 100. Anytime a subroutine is called that many times without returning a result perl issues the deep recursion warning, it can be turned off but its probably a good idea to keep it on unless you really need to ignore the warning for testing purposes or other requirement.

http://perldoc.perl.org/5.8.8/perldiag.html

If the requirement is to get ten sets of unduplicated sets from the range 1-100 then the function should recurse a few times if any. If the requirement is to get nearly all the unduplicated sets (or all) from any range of numbers than recursion is not the way to go, it is too inefficient.

------------------------------------------
- Kevin, perl coder unexceptional!