views:

4475

answers:

4

If you have an NSMutableArray, how do you shuffle the elements randomly?

(I have my own answer for this, which is posted below, but I'm new to Cocoa and I'm interested to know if there is a better way.)

+17  A: 

I solved this by adding a category to NSMutableArray.

Note that this implementation uses random(), so the main application should call srandom() to seed the random number generator before using it.

Edit Removed unnecessary method thanks to answer by Ladd.

//  NSMutableArray_Shuffling.h

#if TARGET_OS_IPHONE
#import <UIKit/UIKit.h>
#else
#include <Cocoa/Cocoa.h>
#endif

// This category enhances NSMutableArray by providing
// methods to randomly shuffle the elements.
@interface NSMutableArray (Shuffling)
- (void)shuffle;
@end


//  NSMutableArray_Shuffling.m

#import "NSMutableArray_Shuffling.h"

@implementation NSMutableArray (Shuffling)

- (void)shuffle
{
    NSUInteger count = [self count];
    for (NSUInteger i = 0; i < count; ++i) {
        // Select a random element between i and end of array to swap with.
        int nElements = count - i;
        int n = (random() % nElements) + i;
        [self exchangeObjectAtIndex:i withObjectAtIndex:n];
    }
}

@end
Kristopher Johnson
Nice solution. And yes, as willc2 mentions, replacing random() with arc4random() is a nice improvement as no seeding is required.
Jason Moore
+9  A: 

You don't need the swapObjectAtIndex method. exchangeObjectAtIndex:withObjectAtIndex: already exists.

Thanks! Don't know why I didn't notice that in the docs.
Kristopher Johnson
+1  A: 

Take a look at this question: Real-world problems with naive shuffling with respect to your shuffling algorithm.

craigb
I believe I am not using the "naive" shuffle, but am in fact using the Knuth algorithm. Am I wrong?
Kristopher Johnson
Yes, you are using the Knuth algorithm --- but until I read the information at the other end of the link, I didn't notice the difference.
benzado
if you drop in arc4random(), you won't have to seed, right?
willc2
+2  A: 

This is the simplest and fastest way to shuffle NSArrays or NSMutableArrays (object puzzles is a NSMutableArray, it contains puzzle objects. I've added to puzzle object variable index which indicates initial position in array)

int randomSort(id obj1, id obj2, void *context ) {
        // returns random number -1 0 1
    return (random()%3 - 1); 
}

- (void)shuffle {
        // call custom sort function
    [puzzles sortUsingFunction:randomSort context:nil];

    // show in log how is our array sorted
        int i = 0;
    for (Puzzle * puzzle in puzzles) {
     NSLog(@" #%d has index %d", i, puzzle.index);
     i++;
    }
}

log output:

 #0 has index #6
 #1 has index #3
 #2 has index #9
 #3 has index #15
 #4 has index #8
 #5 has index #0
 #6 has index #1
 #7 has index #4
 #8 has index #7
 #9 has index #12
 #10 has index #14
 #11 has index #16
 #12 has index #17
 #13 has index #10
 #14 has index #11
 #15 has index #13
 #16 has index #5
 #17 has index #2

you may as well compare obj1 with obj2 and decide what you want to return possible values are:

  • NSOrderedAscending = -1
  • NSOrderedSame = 0
  • NSOrderedDescending = 1
Also for this solution, use arc4random() or seed.
Johan Kool
This shuffle is flawed – as Microsoft has recently been reminded of: http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html.
Raphael Schweikert