canonical way to randomize an NSArray in Objective

Question

Is there a canonical way to randomize an array in Objective C?

Answer 1

NSArray randomization as Objective-C category method:

@implementation NSArray (NGDataDynamics)

- (NSArray *)jumbled
{
  NSMutableArray *jumbled = self.mutableCopy;

  NSUInteger idx = self.count-1;
  while(idx)
  {
    [jumbled exchangeObjectAtIndex:idx
                 withObjectAtIndex:arc4random_uniform(idx)];
    idx--;
  }

  return jumbled;
}

@end

As seen: NSArray Randomization & Psychedelia

Answer 2

My utility library defines this category on NSMutableArray to do it:

@interface NSMutableArray (ArchUtils_Shuffle)
- (void)shuffle;
@end

// Chooses a random integer below n without bias.
// Computes m, a power of two slightly above n, and takes random() modulo m,
// then throws away the random number if it's between n and m.
// (More naive techniques, like taking random() modulo n, introduce a bias 
// towards smaller numbers in the range.)
static NSUInteger random_below(NSUInteger n) {
    NSUInteger m = 1;

    // Compute smallest power of two greater than n.
    // There's probably a faster solution than this loop, but bit-twiddling
    // isn't my specialty.
    do {
        m <<= 1;
    } while(m < n);

    NSUInteger ret;

    do {
        ret = random() % m;
    } while(ret >= n);

    return ret;
}

@implementation NSMutableArray (ArchUtils_Shuffle)

- (void)shuffle {
    // http://en.wikipedia.org/wiki/Knuth_shuffle

    for(NSUInteger i = [self count]; i > 1; i--) {
        NSUInteger j = random_below(i);
        [self exchangeObjectAtIndex:i-1 withObjectAtIndex:j];
    }
}

@end

Make sure you seed the random number generator (with e.g. srandom(time(NULL))) sometime before you call it; otherwise the output won't be very random.

Answer 3

There isn't a canonical way without making a category on NSArray (i.e. have an instance method like arrayWithRandomizedIndices) or NSMutableArray (i.e. have a method like randomizeIndices).

Here's an example from my library, part of a category on NSMutableArray. It will randomly reorder the array, rather than shuffle a few entries.

- (void) randomizeIndices
{
  if (self == nil || [self count] <= 1)
  {
    return;
  }

  int count = [self count];

  NSMutableArray* copySelf = [NSMutableArray arrayWithArray:self];
  NSMutableArray* mutableResultArray = [NSMutableArray alloc];
  mutableResultArray = [mutableResultArray initWithCapacity:count];
  [mutableResultArray autorelease];

  int objectsMovedCount = 0;

  for (int i = 0; i < count; i++)
  {
    int index = rand() % (count - objectsMovedCount);
    id anObject = [copySelf objectAtIndex:index];
    [mutableResultArray addObject:anObject];
    [copySelf removeObjectAtIndex:index];
    objectsMovedCount++;
  }
  [self setArray:mutableResultArray];
}

Call srand(time(0)); or some such before calling this method or early in the method.

Answer 4

Here it is!

- (NSArray*)shuffleArray:(NSArray*)array {

    NSMutableArray *temp = [[NSMutableArray alloc] initWithArray:array];

    for(NSUInteger i = [array count]; i > 1; i--) {
        NSUInteger j = arc4random_uniform(i);
        [temp exchangeObjectAtIndex:i-1 withObjectAtIndex:j];
    }

    return [NSArray arrayWithArray:temp];
}

Answer 5

if ([array count] > 1) {
    for (NSUInteger shuffleIndex = [array count] - 1; shuffleIndex > 0; shuffleIndex--)
        [array exchangeObjectAtIndex:shuffleIndex withObjectAtIndex:random() % (shuffleIndex + 1)];
}

Make sure to seed the random() function with either srandomdev() or srandom().

Answer 6

My solution is a category method that returns a copy of the array (autoreleased) with elements randomised (using arc4random).

@interface NSArray (CMRandomised)

/* Returns a copy of the array with elements re-ordered randomly */
- (NSArray *)randomised;

@end

/* Returns a random integer number between low and high inclusive */
static inline int randomInt(int low, int high)
{
    return (arc4random() % (high-low+1)) + low;
}

@implementation NSArray (CMRandomised)

- (NSArray *)randomised
{
    NSMutableArray *randomised = [NSMutableArray arrayWithCapacity:[self count]];

    for (id object in self) {
        NSUInteger index = randomInt(0, [randomised count]);
        [randomised insertObject:object atIndex:index];
    }
    return randomised;
}

@end