TL;DR sample() works fine.

Background: I had supplied a solution 2-3 weeks ago. I then questioned whether sample() would've been better than shuffle(). I indicated that I'd encountered a potential problem; but real-life got in the way of further testing. I've just noticed that I didn't follow-up on that when real-life got out of the way. :-)

For ease of reference, here's my previous posts which are somewhat scattered throughout the thread:

1. Re: Add a fixed number of unique elements to hash
2. Re^3: Add a fixed number of unique elements to hash [sample() vs. shuffle()]
3. Re^5: Add a fixed number of unique elements to hash [sample() vs. shuffle()]

The OP subsequently wrote that a solution was required that could be used with Perl 5.004; accordingly, this response generally addresses the issue but will not be specifically useful to the OP.

I made two modifications to the code posted in "Re: Add a fixed number of unique elements to hash" that change shuffle() to sample(). I also removed a sort to better highlight the randomness of sample().

...
#use List::Util 'shuffle';
use List::Util 'sample';
...
#my @playlist = (shuffle @all_files)[0 .. $list_length - 1];
my @playlist = sample $list_length, @all_files;
#print "$_\n" for sort @playlist;
print "$_\n" for @playlist;
...
[download]

Here's some sample runs (the updated script is called "rand_select_files_sample.pl"):

ken@titan ~/tmp/pm_11150231_dir_rand_select
$ ./rand_select_files_sample.pl
/home/ken/tmp/pm_11150231_dir_rand_select/inc2/n.x
/home/ken/tmp/pm_11150231_dir_rand_select/a.x
/home/ken/tmp/pm_11150231_dir_rand_select/c.z

ken@titan ~/tmp/pm_11150231_dir_rand_select
$ ./rand_select_files_sample.pl
/home/ken/tmp/pm_11150231_dir_rand_select/inc1/j.z
/home/ken/tmp/pm_11150231_dir_rand_select/c.z
/home/ken/tmp/pm_11150231_dir_rand_select/inc1/h.x

ken@titan ~/tmp/pm_11150231_dir_rand_select
$ ./rand_select_files_sample.pl
/home/ken/tmp/pm_11150231_dir_rand_select/inc1/j.z
/home/ken/tmp/pm_11150231_dir_rand_select/c.z
/home/ken/tmp/pm_11150231_dir_rand_select/a.x
[download]

Clearly, multiple runs are producing different results. I don't have any results from earlier runs using sample(). Assumption: PEBCAC