objective c - What's the Best Way to Shuffle an NSMutableArray?

ID : 20078

viewed : 35

Tags : objective-ccocoashuffleobjective-c

Top 5 Answer for objective c - What's the Best Way to Shuffle an NSMutableArray?

vote vote

96

I solved this by adding a category to NSMutableArray.

Edit: Removed unnecessary method thanks to answer by Ladd.

Edit: Changed (arc4random() % nElements) to arc4random_uniform(nElements) thanks to answer by Gregory Goltsov and comments by miho and blahdiblah

Edit: Loop improvement, thanks to comment by Ron

Edit: Added check that array is not empty, thanks to comment by Mahesh Agrawal

//  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];     if (count <= 1) return;     for (NSUInteger i = 0; i < count - 1; ++i) {         NSInteger remainingCount = count - i;         NSInteger exchangeIndex = i + arc4random_uniform((u_int32_t )remainingCount);         [self exchangeObjectAtIndex:i withObjectAtIndex:exchangeIndex];     } }  @end 
vote vote

82

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

vote vote

76

Since I can't yet comment, I thought I'd contribute a full response. I modified Kristopher Johnson's implementation for my project in a number of ways (really trying to make it as concise as possible), one of them being arc4random_uniform() because it avoids modulo bias.

// NSMutableArray+Shuffling.h #import <Foundation/Foundation.h>  /** This category enhances NSMutableArray by providing methods to randomly  * shuffle the elements using the Fisher-Yates algorithm.  */ @interface NSMutableArray (Shuffling) - (void)shuffle; @end  // NSMutableArray+Shuffling.m #import "NSMutableArray+Shuffling.h"  @implementation NSMutableArray (Shuffling)  - (void)shuffle {     NSUInteger count = [self count];     for (uint i = 0; i < count - 1; ++i)     {         // Select a random element between i and end of array to swap with.         int nElements = count - i;         int n = arc4random_uniform(nElements) + i;         [self exchangeObjectAtIndex:i withObjectAtIndex:n];     } }  @end 
vote vote

70

If you import GameplayKit, there is a shuffled API:

https://developer.apple.com/reference/foundation/nsarray/1640855-shuffled

let shuffledArray = array.shuffled() 
vote vote

57

A slightly improved and concise solution (compared to the top answers).

The algorithm is the same and is described in literature as "Fisher-Yates shuffle".

In Objective-C:

@implementation NSMutableArray (Shuffle) // Fisher-Yates shuffle - (void)shuffle {     for (NSUInteger i = self.count; i > 1; i--)         [self exchangeObjectAtIndex:i - 1 withObjectAtIndex:arc4random_uniform((u_int32_t)i)]; } @end 

In Swift 3.2 and 4.x:

extension Array {     /// Fisher-Yates shuffle     mutating func shuffle() {         for i in stride(from: count - 1, to: 0, by: -1) {             swapAt(i, Int(arc4random_uniform(UInt32(i + 1))))         }     } } 

In Swift 3.0 and 3.1:

extension Array {     /// Fisher-Yates shuffle     mutating func shuffle() {         for i in stride(from: count - 1, to: 0, by: -1) {             let j = Int(arc4random_uniform(UInt32(i + 1)))             (self[i], self[j]) = (self[j], self[i])         }     } } 

Note: A more concise solution in Swift is possible from iOS10 using GameplayKit.

Note: An algorithm for unstable shuffling (with all positions forced to change if count > 1) is also available

Top 3 video Explaining objective c - What's the Best Way to Shuffle an NSMutableArray?

Related QUESTION?