Randomly and non-destructively pick two items without replacement from an array

A. Sinan Unur

Suppose you want to randomly pick a pair of elements from an array without replacement. That is, given [qw(Cat Dog Fox Horse Goose Unicorn)], you want to pick ($first, $second) so that $first ne $second.

One might first try something like this:

#!/usr/bin/env perl

use 5.014;
use strict;
use warnings;

my $set = [qw(Cat Dog Fox Horse Goose Unicorn)];

say "@{ pick1($set) }" for 1 .. 5;

sub pick1 {
    my $set = shift;
    my $n = @$set;

    my $x = $set->[rand $n];
    my $y;

    do {
        $y = $set->[rand $n];
    } until ($x ne $y);

    return [$x, $y];
}

That is not horrible, but can we do better? For example, there is no need to live with the possibility of generating a duplicate when we know we do not want that. splice can help with that:

sub pick2 {
    my $set = shift;

    my @i = (0 .. $#$set);

    my $j = splice @i, rand @i, 1;
    my $k = splice @i, rand @i, 1;

    return [ @{$set}[$j, $k] ];
}

The array of indices of @$set, @i, is there because I do not want the act of picking these pairs to alter the underlying array.

What if $set refers to an array with a large number of elements? Creating @i may be really undesirable in such a case.

But, of course, if you are just picking two elements, you can replace the splice with simple arithmetic:

sub pick3 {
    my $set = shift;

    my $j = int rand(@$set);
    my $k = int rand(@$set - 1);

    $k += ($k >= $j);

    return [ @{$set}[$j, $k] ];
}

Say, @$set has 6 elements. The first invocation of rand picks an index out of {0, 1, 2, 3, 4, 5, 6} and the second invocation picks one from {0, 1, 2, 3, 4, 5}. Say the first index picked was 2. Then, the correct set out of which to pick the second index would be {0, 1, 3, 4, 5, 6}. The line:

    $k += ($k >= $j);

takes care of this mapping.

Of course, for serious work, you should use something like Math::Random::MT rather than whatever rand your runtime gives you.