Select value from array w/o replacement (or destroying the array)

[BioNrd]

Monks, I am currently pondering this conundrum. I have an array of numbers (not shown below), and I need to randomly select a value from that array (n) number of times, without replacement.

I know this is possible with a splice  ($ranpop = splice(@holder, int rand(@holder), 1)); but I do not want to destroy the array.

I was thinking something along these lines:

use strict;
use warnings;
my @final;
my $item;
my @list = (2, 1, 4, 3, 8, 5); #already selected from array
#image another loop someplace else that is pushing into @list

for (1 .. 5) { #getting 5 numbers not on the list above...

my $find = int rand (10); #my "array" I am picking from is 0-10


#below this is my attempt to solve my problem
my $found_flag = 0;

foreach my $item ( @list ) {
    if( $item eq $find ) {
        $found_flag = 1;
        last;
    }
}

if( $found_flag ) {
    print "Found $find.\n";
    until ( $find != $item ) {
        $find = int rand (10);
    }
}

#I tried to basically say
# if (the item is already in the array) {
#     pick a value until it is not found in the array
# }

push @final, $find;
} 
print "@final \n";

But I am doing something wrong, and I can not figure it out. Somewhere or something in that last loop needs to be adjusted. Any help is appreciated.

-Bio

[tye]

Here is a one-at-a-time Fisher-Yates shuffle but using an array of indices instead of modifying your array of numbers directly (if even avoids having to move around half of the extra array via splitsplice):

#!/usr/bin/perl -lw
use strict;

my @inviolable= getNumbers();
my $pickNext= genPickWNoReplace( \@inviolable );
while(  1  ) {
    print $pickNext->();
}

sub genPickWNoReplace
{
    my( $av )= @_;
    my @idx= 0..$#$av;
    return sub {
        die "No more items left to pick from"
            if  ! @idx;
        my $o= int rand @idx;
        my $pick= $av->[ $idx[$o] ];
        $idx[$o]= $idx[-1];
        pop @idx;
        return $pick;
    };
}

(update above thanks to fenLisesi's correction)

[kyle]

Why not copy the array and destroy the copy? Is it big?

An easy solution would involve List::Util::shuffle. Just shuffle the (copied) array and pop n items off of it.

If you really can't copy the array, maybe this would work:

# 20 random integers, 0-99
my @orig_list = map { int rand 100 } 0 .. 20;
my @selected = ();   # items selected
my $desired = 10;    # how many items to select
my %found = ();      # indexes already used
while ( scalar @selected < $desired ) {
    my $index;
    $index = int rand @orig_list until ! $found{$index}++;
    push @selected, $orig_list[$index];
}

Note that this is not very efficient when the number of items desired approaches the size of the original list. However, it avoids copying the whole list or modifying any part of it.

[tachyon-II]

The traditional way to do this task is to shuffle the array and then just select sequential values from it. See How do I shuffle an array?

If you need to preserve the order then you just shuffle a temporary array (that initially held sequential index values) and select sequential values from that to get random index values to your original array.

[Gangabass]

My suggestion is to use hash:

my %already_selected;

......
unless ( $already_selected{$find} ) {
    $already_selected{$find}++;
    #this number is selecting first time
    ....
}

And of course don't use splice if you don't want destroy original array.

[BioNrd]

Thank you all for the ideas. One of these should work out great.

[moritz]

As a side note, Perl 6 has the pick builtin, which does what BioNrd wants:

my @picked    = @list.pick(3); # randomly pick 3 elements;
my @shuffled  = @list.pick(*); # same as List::Util::shuffle

[fenLisesi]

I think tye's solution is the best. If for some reason you would prefer one of the others, the answer would depend on how big n is compared to the size of the array. If it is small, say, smaller than 10%, then just pick a random number in the range 0..$#a and pick another one if that had been picked before. Such collisions should be rare for small n / @a; If it is larger, then shuffle first, but do not shuffle the array itself, especially if the array elements themselves tend to be big (which doesn't seem to be the case here). Instead, create a separate index array and shuffle that -- something like @indices = shuffle 0..$#a. Below, I tried to add comments to tye's code. I may have messed up, so wait until wiser monks have had a chance to peruse it.

use strict;
use warnings;

## How many elements to pick
use constant N => 10;

## The original array that must not be altered
my @letters = ('a'..'z');

##-----------------------------------------------------+
## Generate code that will pick an element from
##     @letters at each iteration without repeating
##-----------------------------------------------------+
my $picker_of_next_rand = gen_picker( \@letters );

## Now execute (iterate) that code N times
for (1..N) {
    print $picker_of_next_rand->();
}
print "\n";            ## look nice
print @letters, "\n";  ## original untouched
exit( 0 );

##-----------------------------------------------------+
## This sub generates and returns code that will pick
##     a random element from @$aref at each iteration
##     without repeating
##-----------------------------------------------------+
sub gen_picker {
    my ($aref) = @_;
    my @indices = 0 .. $#$aref;

    ## closes on @indices
    return sub {
        if (! @indices) {
            die "No more items left to pick from";
        }

        ##---------------------------------------------+
        ## pick an int in the range (0 .. $#$aref),
        ## the range of the array's indices
        ##---------------------------------------------+
        my $random_index = int rand @indices;

        ## $pick is the element at the random_index
        my $pick = $aref->[ $indices[ $random_index ] ];

        ##---------------------------------------------+
        ## We are about to pop the index array.  Save
        ## the element at the pop-end of the index array
        ## by copying it into the position of the $pick
        ## (clobber index of $pick, won't be used again)
        ##---------------------------------------------+
        $indices[ $random_index ] = $indices[ -1 ];

        ## Now it is safe to pop the index array
        pop @indices;

        return $pick;
    };
}

which prints something like the following:

vkdbfymxie
abcdefghijklmnopqrstuvwxyz

[BioNrd]

I agree that this solution is going to suit my needs. The code works really well, but I don't understand a part of it.

my $picker_of_next_rand = gen_picker( \@letters );

print $picker_of_next_rand->();

I under stand that is is a reference/dereference type thing.

What I don't understand is how to use the variable $pick in a meaningful (non-global) way. i.e. $var_to_use_later = $list[$pick]; I have had trouble with reference/dereference structure before, and I have tried to use the camal book. It is not sinking in, and combined with a bit of code I am not familar with...it is a headache for me.

I appreciate all that has been done to this point for me, it is just that last little push in the right direction I need.

Thanks...Bio.