davorg,
Great advice and I upvoted you. It is nice to point out though that this, and randomly splicing elements of the original array do not leave it intact. Apparently Data::Random can do this as well as my suggestion of using a parallel array of indices.

Update: After looking at the source of Data::Random's rand_set(), I noticed the routine can be terribly run-time inefficient depending on the parameters. It continously selects random indices until it finds enough unique ones to satisfy the 'size' option. This is doing a lot more work than necessary. I have emailed the author with suggestions.