38

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

2

7 Answers 7

59

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.

8
  • Love it! Thanks for sharing. I'm extremely curious about the rest of your utility library now.
    – PEZ
    Jan 11, 2011 at 19:51
  • 6
    @bresc either seed random with srandom(time(NULL)) or use arc4random() instead Apr 27, 2011 at 19:09
  • 1
    Just a small thing I added: if (n == 0) { return 0; }. You could just not pass 0 but if you do you get trapped in that second loop. Sep 20, 2011 at 0:22
  • 12
    If you are using OSX 10.7 or iOS 4.3 or later you can use arc4random_uniform(upper_bound) and not have to write or use the random_below(i) function.
    – LavaSlider
    Jan 16, 2012 at 14:20
  • 1
    @LavaSlider Good point! Here's the implementation stackoverflow.com/a/10258341/396133
    – Abramodj
    Apr 21, 2012 at 11:02
20

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];
}
7
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().

3
  • What you wrote doesn't make sense as an instance method. As the code exists, it should just be a function or class method. Idiomatically, it should be an NSArray instance method that returns a new, shuffled array or an NSMutableArray instance method that shuffles itself.
    – Chuck
    Apr 26, 2009 at 18:41
  • True, I was just demonstrating the code here, wasn't really worried about putting it in a category. I also forgot to mention to seed the random() function with srandomdev() or srandom(). Apr 26, 2009 at 19:24
  • 2
    This code is slightly biased due to the modulo; see en.wikipedia.org/wiki/Fisher-Yates_shuffle#Modulo_bias for more about this. Apr 26, 2009 at 22:36
2

There is none built into the SDK if that's what you are asking.

You can use just about any randomization or shuffling algorithm you want however. Different algorithms have different tradeoffs in terms of randomness, efficiency, etc.

http://en.wikipedia.org/wiki/Shuffling#Shuffling_algorithms

For algorithms that shuffle "in-place" start with a mutable array use

insertObject:atIndex:
removeObjectAtIndex:

For algorithms that reconstruct the array, feed it the original and build a new array.

1

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
0

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.

0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.