use Data::Dumper;

my @a = (1..4);
my $len = 4;

print Dumper(combinations($len, @a));

sub combinations
{
        my ($size, @elements) = @_;
        return [] if $size < 1;

        my @result = ();

        foreach my $elem (@elements)
        {
               push @result,
                    map { [$elem, @$_] }
                    combinations($size-1,
                          grep { $_ != $elem }
                          @elements)
        }

        return @result;
}
[download]

Update: for greater generality, replace foreach loop with

my @seen = ();
while (@elements)
{
     my $elem = shift @elements;
     push @result,
         map { [$elem, @$_] }
         combinations($size-1, @seen, @elements);
     push @seen, $elem;
}
[download]