Selecting n random entries from a list

I have an array of N items from which I want to be able to select M distinct random items where M < N.

I've currently implemented this by selecting a random index, checking whether it has 开发者_运维问答already been selected, and if not using it in my subset. The problem is, this requires me to store a list of already chosen items so that I know if I've already used one.

Is there a way to generate random numbers that span a set of indices but don't repeat until they loop back to the beginning?

Cheers in advance

In case you can destroy the original array:

select a random element position between 0 and N-1, get selected element. Move the last element of the array to the position of the selected one. Now you have one element less in the array. You can repeat this process M times.

The first element has M/Nchance of being chosen, so select it with this probability and proceed recursively or iteratively.

In pseudocode, where rand(k) would give a random integer uniformly chosen between 1 and k:

for (i = N to 1)
{
   if (rand(i) <= M)
   {
      choose i;
      M--;
   }
}

There are N choose M = N! / ((N-M)!M!) possible subsets to choose, so select some ordering of these subsets, then select a random number between 1 and N choose M, and then use that subset.

For example, if N = 3 and M = 2, your ordering could be {1,2}, {1,3}, {2,3}, and so you'd pick a random number from 1 to 3 and then take the corresponding elements (1 -> {1,2}, 2 -> {1,3}, 3 -> {2,3}).