Choosing a subset in uniformly random manner?

Question is:

Write a method to randomly generate a set of m integers from an array of size n. E开发者_运维技巧ach element must have equal probability of being chosen.

Is this answer correct?:

I pick a first integer uniformly randomly. pick next. if it already exists. I don't take it else take it. and continue till I have m integers.

let m be the number of elements to select
for i = 1; i <= m; i++
   pick a random number from 1 to n, call it j
   swap array[j] and array [n] (assuming 1 indexed arrays)
   n-- 

At the end of the loop, the last m elements of array is your random subset. There is a variation on fisher-yates shuffle.

There are 2^n subsets. Pick a number between 0 and 2^n-1 and turn that into binary. Those with bits set should be taken from the array and stored.

e.g. Consider the set 1,2,3,4.

int[] a = new int[]{ 1, 2, 3, 4 }
int n = (2*2*2*2) - 1; // 2^n -1 
int items = new Random().nextInt(n);

// If items is 3 then this is 000011 so we would select 1 and 2
// If items is 5 then this is 000101 so we would select 1 and 3
// And so on
for (int i=0;i<a.length;++i) {
   if ((items & (1 << i)) != 0) {
       // The bit is set, grab this item
       System.out.println("Selected " + a[i]);
   }
}

Think of your original range to choose from as a list from 1-n, when you choose an element (number) remove that element from the list. Choose elements based on list index, rather than the actual number value.

int Choose1(List<int> elts)
{
    var idx = rnd.Next(0,elts.Count);
    var elt = elts[idx];
    elts.RemoveAt(idx);
    return elt;
} 

public List<int> Choose(int fromN, int chooseM)
{
    var range = new List<int>();
    for (int i = 1; i <= fromN; i++)
    {
        range.Add(i);
    }
    var choices = new List<int>();
    for (int i = 0; i < chooseM; i++)
    {
        choices.Add(Choose1(range));
    }
    return choices;
}

Using lists won't be efficient for large numbers, but you can use the same approach without actually constructing any lists, using a bit of arithmetic.

If your picks are random then the probability of picking m items in the manner you described would be 1/pow(n,m). I think what you need is 1/C(n,m).