push @num, splice(@array, int rand @array, 1);
[download]

Paladin,
Wow. That certainly is much neater than my solution. I knew there were likely canned solutions, but it seemed like a cool problem to solve:

#!/usr/bin/perl
use strict;
use warnings;

print "$_\n" for Get_Unique_Random(10 , 3);

sub Get_Unique_Random {
    my ($max , $total) = @_;
    #  Requires error checking obviously
    $total ||= 3;
    my @return;
    while ( @return < $total ) {
         my @list = ( 1 .. $max );
         for my $seen ( @return ) {
             @list = grep { $_ ne $seen } @list;
         }
         push @return , $list[ (int rand $#list) + 1 ];
    }
    return wantarray ? @return : \@return;
}
[download]

Cheers - L~R

Honestly,

push @num, splice(@array, int rand @array, 1);
[download]

This totally made my day - the efficiency. In an extension of the original requirement, I needed to generate long fixed length strings from random elements in an array.. this is so much faster than what I was using.. I've no absolute requirement for total uniqueness, but it looks like no letter is being repeated in multiple runs of:

#!/usr/bin/perl -w

use strict;

my $counter = "0";
my $randstring;
my @testarray = ( 'a' .. 'z', 'A' .. 'Z', '0' .. '9' );

do { $randstring .= splice(@testarray, int rand @testarray,1); 
     ++$counter;
} until $counter == 62; 

print "\n\$randstring:  $randstring\n\n";
[download]

-hsinclai

The List::Util module has a good (fast and suitably random) array shuffler, and then three simple pops or shifts will give you the first three choices.

use List::Util qw(shuffle);
my @random = ( shuffle 1 .. 10 )[ 0 .. 2 ];
[download]

my @population = (1..10); # destructive source
my $n = 3; # desired selection size
my @selection; # result appears here
while (@selection < $n) {
  my $swapper = int rand @population;
  push @selection, $population[$swapper];
  if ($swapper < $#population) {
    $population[$swapper] = $population[-1];
  }
  pop @population;
}
[download]

Urgle. While you pick a fast algorithm, your implementation is not efficient. There's no need to build @selection element by element, while popping off one element of of @population at the time. Just run $n iterations of Fisher-Yates loop, and return the last $n elements of the array. Furthermore,

if ($swapper < $#population) {
    $population[$swapper] = $population[-1];
}
[download]

is less efficient than

$population[$swapper] = $population[-1];
[download]

Sure, the if statement prevents a needless assignment, but the expected number of needless assignments is

Σi=0$n 1/(@population - i)

which, while unbounded, grows very very slowly if the array to sample grows. OTOH, the number of compares done is linear with the size of the sample taken.

Abigail

Oddly enough, Abi, I was hoping you'd point out the error of my ways. You have a brilliance that I can only aspire towards. I'm just a street-trained programmer of average class.

-- Randal L. Schwartz, Perl hacker
Be sure to read my standard disclaimer if this is a reply.

Out of curiosity, why did you choose to build a new list instead of transposing items within the existing one:

    my @sample = (1..10);
    my $n = 3;
    
    for my $l (0..$n-1) {
        my $r = rand (@sample);
        @sample[ $l, $r ] = @sample[ $r, $l ];
    }
    
    print join (", ", @sample[0..$n-1]), "\n";
[download]

Transposition is safe against multiple hits to the same index, since each swap just shuffles the list a bit more. That eliminates the need to cull values that have already been seen, as you do with the pop at the tail of your loop.

Even the degenerate case, where $l equals $r, leaves the list no less shuffled than it was before. And since every non-degenerate swap exchanges two values in the list, even the value left in place by a degenerate swap has a good chance of being moved by another, later swap.

my @num;
my @array = 1 .. 10;
for (1..3) {
    push @num, splice(@array, rand(@array), 1);
}
[download]

You have the write code to select a single random element from the array. To get unique random numbers, you need to remove that element from the array and then keep selecting from the shorter set.

Luckely, you don't have to. While it hardly matters for an array of 10 elements, the principle doesn't scale. splice is an expensive operation, whose expected run time is Θ (N) for a single delete. If you have to select k elements from an array of size N, you have an expected running time of Θ (k * N). OTOH, if you perform a partial Fisher-Yates shuffle (you only need to get k elements), your running time reduces to O (k) (after setting up the array).

Abigail

I didn't think about the efficiency of splice. I originally had it coded to shuffle after selecting the element. In other words, select the random element, swap the last element with the selected one, and shorten the array. Technically, the array does not need to be shortened.

First, just don't call srand, it isn't useful here. At least you didn't pass an argument to it. :)

I find it unfortunate that List::Util's shuffle() doesn't support stopping the shuffle process after the first N new items have been selected. This makes using it for this situation somewhat inefficient. But to really make it inefficient, you should pick from a really huge list. But, having a really huge list means this method becomes inefficient in memory as well as in wasting a lot of time doing shuffling that doesn't matter.

So here is a solution that scales very well as far as memory and CPU use is concerned. It isn't as flexible (it only lets you select from a range of integers) and it probably isn't even faster for such small cases as originally requested, but it was an interesting challenge. Maybe I should add it to Algorithm::Loops.

It uses the same algorithm as the Fisher-Yates shuffle, but using a sparse array.

use strict;
use warnings;

# My solution:
sub pickInts {
    my( $count, $min, $max )= @_;
    my( @pick, %pick );
    while(  0 < $count--  ) {
        my $i= int( $min + rand($max-$min+1) );
        for(  $pick{$i}  ) {
            $i= $_   if  defined;
            $_= $min++;
        }
        push @pick, $i;
    }
    return wantarray ? @pick : \@pick;
}

# For comparison:
#use List::Util qw( shuffle );
# I don't have this module, so I stole its code:
sub shuffle (@) {
  my @a=\(@_);
  my $n;
  my $i=@_;
  map {
    $n = rand($i--);
    (${$a[$n]}, $a[$n] = $a[$i])[0];
  } @_;
}

# Sample uses:

# Pick 3 integers from the range 1..10:
my @list= pickInts( 3, 1, 10 );
print "@list\n";
print join " ", (shuffle(1..10))[0..2], $/;

$|= 1;
# Pick 10 integers from the range 100000..999999:
@list= pickInts( 10, 100000, 999999 );
print "@list\n";
print join " ", (shuffle(100000..999999))[0..9], $/;
[download]

which produces the output like:

> perl pick.pl
2 1 9
4 10 9
676232 765332 337745 257079 672444 306794 410807 382463 952100 532838
^C
>
[download]

Sorry, I didn't have time to wait for the full output. (:

I was just looking at the code here and it struck me that there must be a simpler way than having to mess with lists.

Suppose I have to pick just one random number from the range 1..10. I can do it by using the following code:

sub pick_one
  {
    my($from,$to) = @_;
    for(my $i=$from;$i<=$to;$i++)
      {
        return $i if(rand(1) <= 1/($to-$i+1));
      }
  }
[download]

(Notice that when $i==$to the test must always succeed so we don't have to worry about a final return)

If I have to pick $n more numbers and I have ($to-$from+1) numbers left then the chance that the next number will be one of those picked is ($n/($to-$from+1)), so the final form of the subroutine is:

sub pick_n
  {
    my($n,$from,$to) = @_;
    my(@picked);

    for(my $i=$from;$i<=$to;$i++)
      {
        if(rand(1) <= ($n/($to-$i+1)))
          {
            push(@picked,$i);
            $n--;
          }
      }
    return @picked;
  }
[download]

Without having to shuffle lists or even use them. Notice the time is always the proportional to the range and the results are always unique. Just to prove that the results are fair:

my(@counts);

for(my $i=0;$i<100000;$i++)
  {
    foreach my $c (pick_n(3,1,10))
      {
        $counts[$c]++;
      }
  }

for(my $c=0;$c<=$#counts;$c++)
  {
    print "Count[$c] = $counts[$c]\n";
  }
[download]

=>

Count[0] =
Count[1] = 29974
Count[2] = 30044
Count[3] = 29860
Count[4] = 29949
Count[5] = 30167
Count[6] = 30253
Count[7] = 29808
Count[8] = 30092
Count[9] = 29830
Count[10] = 30028
[download]

Update: This algorithm will work well if there are lots of numbers to be selected from a shorter list. If selecting fewer numbers from longer lists then the simple hash approach that most other suggestions are based on will be more efficient.

Very nice.

Take another look at my solution (which also doesn't deal with a list). For picking relatively few items from large ranges, my solution should be much faster than yours. But I can certainly see situations where I'd prefer yours over mine (for example, if I wanted the items returned in sorted order).

I plan to make iterator versions of both.

- tye        

my @num = map { int( 1 + rand 10 ) } (1..3);
[download]

my %num;
while(keys %num < 3) {
   my $x =  int( 1 + rand 10 );
   $num{$x}++ unless exists $num{$x};
}
my @num = keys %num;
[download]

A better method is something like this:

@arr=1..10;
for (1..3) {
  $i=int(rand(scalar @arr));
  push(@num,splice(@arr,$i,1));
}

foreach my $num (@num){ print"$num\n"; }
[download]

[me@host]$ perl -le 'print join(",", map { splice (@{$x ||= [1..10]},i
+nt rand @$x,1) } (1..3))'
5,1,8
[me@host]$
[download]

------------
:Wq
Not an editor command: Wq
[download]

Update: Even better:

perl -le '@list=1..10;for(1..3){push @list,shift @list for 1..rand 10;
+ print pop @list}
[download]

perl -le '@n=(1..10);while(@l<3){push@l, splice@n,int rand@n,1}print for@l'


-Waswas

or... perl -le '@l=sort{rand$_<=>rand$_}(1..10);print for@l[0..2]]'


-Waswas

#!/usr/bin/perl

use strict;

my %chosen; # you don't need a 10-element array to draw from

while ( keys %chosen < 3 ) {
    my $pick = int( rand(10)) + 1;
    $chosen{$pick} = undef;
}

print join " ", keys %chosen, "\n";

# (you could "sort {$a<=>$b) keys %chosen", if that matters)
[download]

#!/usr/perl
use warnings;
use strict;

my @tmpary = ();
my @num = ();
my $ulmt = 10;
my $nrneeded = 3;
    
srand;

# if the order of selection of random number is not important
my $idx = 0;
my $cntr = 0;

# this does waste the 1st element but simplifies indexing
# and does cost the memory but for small lists this isn't
# significant
    push @tmpary, undef for (0..$ulmt);

while($cntr < $nrneeded){
    $idx = int(rand($ulmt-1)+1); # map range into (1..ulmt)
    unless($tmpary[$idx]){
        $cntr++;
        $tmpary[$idx] = 1;
    }
}
$tmpary[$_] && push @num, $_ for (0..$ulmt);
print "$_, " foreach (@num);
print "\n";
    
# if order of selection of random numbers is important
my %idx = ();
my $val = 0;
@num = ();
while(scalar keys %idx < $nrneeded){
    $val = int(rand($ulmt-1)+1);   # map range to (1..ulmt)
    $idx{$val} ||= 1 && push @num, $val;
}
print "$_, " foreach (@num);
print "\n";

exit;
[download]