How can I efficiently select several unique random numbers from 1 to 50, excluding x?

Question

I have 2 numbers which are between 0 and 49. Let's call them x and y. Now I want to get a couple of other numbers which are not x or y, but are also between 0 and 49 (I am using Objective C but this is more of a general theory question I think?).

Method I thought of is:

 int a;
 int b;
 int c;

 do {
  a = arc4random() % 49;
 } while ((a == x) || (a == y));

 do {
  b = arc4random() % 49;
 } while ((b == x) || (b == y) || (b == a));

 do {
  c = arc4random() % 49;
 } while ((c == x) || (c == y) || (c == a) || (c == b));

But it seem kind of bad to me, I don't know, I am just trying to learn to be a better programmer, what would be the most elegant way to do this for best practices?

Answer 1

You should shuffle an array of numbers (of values [0, ..., 49] in your case; you can also exclude your x and y from that array if you already know their values), then grab the first N values (however many you're seeking) from the shuffled array. That way, all the numbers are randomly of that range, and not "seen before".

Answer 2

You can use something called the Fisher-Yates shuffle. It's an efficient algorithm for producing a randomly ordered list of values from some set. You would first exclude N from the list of values from which to get random values, and then perform the shuffle.

Answer 3

I'd do something more along the lines of:

NSMutableSet * invalidNumbers = [NSMutableSet set];
[invalidNumbers addObject:[NSNumber numberWithInt:x]];
[invalidNumbers addObject:[NSNumber numberWithInt:y]];

int nextRandom = -1;
do {
  if (nextRandom >= 0) {
    [invalidNumbers addObject:[NSNumber numberWithInt:nextRandome]];
  }
  nextRandom = arc4random() % 49;
} while ([invalidNumbers containsObject:[NSNumber numberWithInt:nextRandom]]);

Answer 4

You could add x, y and the new number to a data structure that you can use as a set and do something like (in pseudo-code; the set structure needs something like push to add values and in for checking membership):

number_of_randoms = 2;

set.push(x);
set.push(y);

for (i = 0; i<number_of_randoms; i++) {
  do {
    new_random = arc4random() % 49;
  } while !set.in(new_random);
  set.push(new_random);
}

So if objc has something appropriate, this is easy...[aha, it does, see Dave DeLong's post].

This algorithm makes sense if number_of_randoms is much less than 49; if they are comparable then you should one of the shuffle (aka permutation) ideas.

Answer 5

First, make a set of valid numbers:

// Create a set of all the possible numbers
NSRange range = { 0, 50 };// Assuming you meant [0, 49], not [0, 49)
NSMutableSet *numbers = [NSMutableSet set];
for (NSUInteger i = range.location; i < range.length; i++) {
    NSNumber *number = [NSNumber numberWithInt:i];
    [numbers addObject:number];
}

// Remove the numbers you already have
NSNumber *x = [NSNumber numberWithInt:(arc4random() % range.length)];
NSNumber *y = [NSNumber numberWithInt:(arc4random() % range.length)];
NSSet *invalidNumbers = [NSSet setWithObjects:x, y, nil];
[numbers minusSet:invalidNumbers];

Then, if you don't need the numbers to be guaranteed to be random, you could use -anyObject and -removeObject to pull out a couple of other numbers. If you do need them to be random, then follow LBushkin's answer, but be careful not to accidentally implement Sattolo's algorithm:

// Shuffle the valid numbers
NSArray *shuffledNumbers = [numbers allObjects];
NSUInteger n = [shuffledNumbers count];
while (n > 1) {
    NSUInteger j = arc4random() % n;
    n--;
    [shuffledNumbers exchangeObjectAtIndex:j withObjectAtIndex:n];
}