iOS: How do I generate 8 unique random integers?

Question

I need to generate 8 random integers, but they need to be unique, aka not repeated.

For example, I want 8 numbers within the range 1 to 8.

I've seen arc4random but I'm not sure how to make them unique ?

Solution

-(NSMutableArray *)getRandomInts:(int)amount from:(int)fromInt to:(int)toInt {

  if ((toInt - fromInt) +1 < amount) {
      return nil;    
  }

  NSMutableArray *uniqueNumbers = [[[NSMutableArray alloc] init] autorelease];
  int r;
  while ([uniqueNumbers count] < amount) {

      r = (arc4random() % toInt) + fromInt;
      if (![uniqueNumbers containsObject:[NSNumber numberWithInt:r]]) {
          [uniqueNumbers addObject:[NSNumber numberWithInt:r]];
      }
  }
  return uniqueNumbers;
}

Answer 1

-(NSMutableArray *)getEightRandom {
  NSMutableArray *uniqueNumbers = [[[NSMutableArray alloc] init] autorelease];
  int r;
  while ([uniqueNumbers count] < 8) {
    r = arc4random();
    if (![uniqueNumbers containsObject:[NSNumber numberWithInt:r]]) {
      [uniqueNumbers addObject:[NSNumber numberWithInt:r]];
    }
  }
  return uniqueNumbers;
}

If you want to restrict to numbers less than some threshold M, then you can do this by:

-(NSMutableArray *)getEightRandomLessThan:(int)M {
  NSMutableArray *uniqueNumbers = [[[NSMutableArray alloc] init] autorelease];
  int r;
  while ([uniqueNumbers count] < 8) {
    r = arc4random() % M; // ADD 1 TO GET NUMBERS BETWEEN 1 AND M RATHER THAN 0 and M-1
    if (![uniqueNumbers containsObject:[NSNumber numberWithInt:r]]) {
      [uniqueNumbers addObject:[NSNumber numberWithInt:r]];
    }
  }
  return uniqueNumbers;
}

If M=8, or even if M is close to 8 (e.g. 9 or 10), then this takes a while and you can be more clever.

-(NSMutableArray *)getEightRandomLessThan:(int)M {
  NSMutableArray *listOfNumbers = [[NSMutableArray alloc] init];
  for (int i=0 ; i<M ; ++i) {
    [listOfNumbers addObject:[NSNumber numberWithInt:i]]; // ADD 1 TO GET NUMBERS BETWEEN 1 AND M RATHER THAN 0 and M-1
  }
  NSMutableArray *uniqueNumbers = [[[NSMutableArray alloc] init] autorelease];
  int r;
  while ([uniqueNumbers count] < 8) {
    r = arc4random() % [listOfNumbers count];
    if (![uniqueNumbers containsObject:[listOfNumbers objectAtIndex:r]]) {
      [uniqueNumbers addObject:[listOfNumbers objectAtIndex:r]];
    }
  }
  [listOfNumbers release];
  return uniqueNumbers;
}

Answer 2

Uniqueness is something that you need to provide-- randomness APIs won't do this for you.

As has been suggested, you can generate a number and then check to see whether it collides with something you've already generated, and if so, try agin. Please note however, that depending on the quantity of numbers and the size of the range, this becomes an algorithm that doesn't have a guaranteed end point.

If you're really just trying to get a contiguous set of numbers in random order, this is a not the way to do it, since it could take an unpredictably long time to complete. In this case, building an array of all desired values first, and then "shuffling" the array is a better choice. The best shuffle is the Fisher-Yates, but if you don't need it to be perfectly unbiased, you could also do what's described here.

Answer 3

Checking for already generated numbers is potentially expensive (theoretically, it could take forever.) However, this is a solved problem. You want a shuffling algorithm, like the Fisher-Yates_shuffle

On iOS probably something like:

NSMutableArray *randSequence = [[NSMutableArray alloc] initWithCapacity:8];
for (int ii = 1; ii < 9; ++ii)
    [randSequence addObject:[NSNumber numberWithInt:ii]];

for (int ii = 8; ii > 0; --ii) {
    int r = arc4random() % (ii + 1);
    [randSequence exchangeObjectAtIndex:ii withObjectAtIndex:r];

// you can now iterate over the numbers in `randSequence` to get
// your sequence in random order

Answer 4

Store the numbers in an array, and each time you generate the next - check if it already exists in the array. If not, then add it and continue.