What's the Best Way to Shuffle an NSMutableArray?

Question

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.)

---

Update: As noted by @Mukesh, as of iOS 10+ and macOS 10.12+, there is an -[NSMutableArray shuffledArray] method that can be used to shuffle. See https://developer.apple.com/documentation/foundation/nsarray/1640855-shuffledarray?language=objc for details. (But note that this creates a new array, rather than shuffling the elements in place.)

Saurian

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

Here is an implementation in Swift: iosdevelopertips.com/swift-code/swift-shuffle-array-type.html – Saurian

Current best is Fisher-Yates: for (NSUInteger i = self.count; i > 1; i--) [self exchangeObjectAtIndex:i - 1 withObjectAtIndex:arc4random_uniform((u_int32_t)i)]; – Francis

Guys , from iOS 10++ new concept of shuffle array given by Apple, Look at this answer – Ite

Problem with existing API is it returns a new Array which addresses to new location in the memory. – Tetrad

Answer 1

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

Bigotry

Answer 2

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

Saurian

Nice solution. And yes, as willc2 mentions, replacing random() with arc4random() is a nice improvement as no seeding is required. – Electrokinetic

@Jason: Sometimes (e.g. when testing), being able to supply a seed is a good thing. Kristopher: nice algorithm. It's an implementation of the Fisher-Yates algorithm: en.wikipedia.org/wiki/Fisher-Yates_shuffle – Aret

It is generally better to use arc4random() instead of random(). The quality of the numbers is much better and seeding is not required. – Law

A super minor improvement: in the last iteration of the loop, i == count - 1. Doesn't that mean that we are exchanging the object at index i with itself? Can we tweak the code to always skip the last iteration? – Behold

I've also added a boolean "bool shuffled = false;" before the loop. During the loop I'm checking "if (i != n) shuffled = true;". And after the loop I'm checking if things has been shuffled: "if (!shuffled) [self shuffle];" because I had a lot of array with 3 items which didn't shuffle on a regular basis. – Chaconne

@Thomas, there are only six ways to order a 3-item array, so you would expect things to come out "unshuffled" about 1/6 of the time. If you reshuffle whenever that happens, then the result isn't very random. – Saurian

True, but my items always need to be shuffled. – Chaconne

Do you consider a coin to be flipped only if the result is the opposite of the side that was originally up? – Saurian

I prefere using arc4random_uniform(nElements) instead of arc4random() % nElements. Also use enumerateObjects instead of for. Sample: sourcedrop.net/Uyy787e411c71 – Weise

i used that but how to call that method i doesen't find the solution – Francisfrancisca

This shuffle is subtly biased. Use arc4random_uniform(nElements) instead of arc4random()%nElements. See the arc4random man page and this explanation of modulo bias for more info. – Ophidian

Instantiate NSInteger:s inside the loop? I wouldn't do that... also, I always do const NSUInteger COUNT = [self count];. – Valletta

@Valletta NSInteger is just a typedef for int or long. "Instantiating" them isn't expensive, and the compiler will probably optimize them away. – Saurian

Can you please add an if clause just to check if the count is more than 0 or not. Because if array is empty and this is called from somewhere then it will cause problem. also a safe side checking for the exchange index if it's beyond the arrays bounds or not and also if it's negative or not. – Parceling

@MaheshAgrawal Thanks. I added the check for count being less than 1, which would indeed cause problems. I don't think an additional check for the exchange index is needed because it can't possibly be out of bounds, due to how it is initialized. – Saurian

@KristopherJohnson thanks for adding. and you are right. actually at first when i was debugging it gave me some out of bounds values but later i understood that was because of less than 0. no need of out of bounds checking because you have already added checking. – Parceling

@KristopherJohnson, Should the last edit be if (count <= 1) return;? Why would someone shuffle an array with 1 element? – Pecker

Answer 3

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

Formulary

Note that you are calling [self count] (a property getter) twice on each iteration through the loop. I think moving it out of the loop is worth the loss of conciseness. – Saurian

And that's why I still prefer [object method] instead of object.method: people tend to forget that the later is not as cheap as accessing a struct member, it comes with the cost of a method call... very bad in a loop. – Parkland

Thank you for the corrections - I wrongly assumed count was cached, for some reason. Updated the answer. – Formulary

Answer 4

If you import GameplayKit, there is a shuffled API:

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

let shuffledArray = array.shuffled()

Frederico

I have myArray and want to create a new shuffleArray of it . How do I do it with Objective - C ? – Cerebration

shuffledArray = [array shuffledArray]; – Frederico

Note that this method is part of GameplayKit so you have to import it. – Curator

Answer 5

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

Shore

What would be the difference between this and Kristopher Johnson's algorithm? – Pecker

@IulianOnofrei, originally, Kristopher Johnson's code was not optimal and I improved his answer, then it got edited again with some useless initial check added. I prefer my concise way of writing it. The algorithm is the same and is described in literature as "Fisher-Yates shuffle". – Francis

Answer 6

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

Honeysucker

Also for this solution, use arc4random() or seed. – Clamor

This shuffle is flawed – as Microsoft has recently been reminded of: robweir.com/blog/2010/02/microsoft-random-browser-ballot.html. – Bonzer

Agreed, flawed because "sorting requires a self-consistent definition of ordering" as pointed out in that article about MS. Looks elegant, but isn't. – Revanche

Answer 7

From iOS 10, you can use NSArray shuffled() from GameplayKit. Here is an helper for Array in Swift 3:

import GameplayKit

extension Array {
    @available(iOS 10.0, macOS 10.12, tvOS 10.0, *)
    func shuffled() -> [Element] {
        return (self as NSArray).shuffled() as! [Element]
    }
    @available(iOS 10.0, macOS 10.12, tvOS 10.0, *)
    mutating func shuffle() {
        replaceSubrange(0..<count, with: shuffled())
    }
}

Shore

Answer 8

There is a nice popular library, that has this method as it's part, called SSToolKit in GitHub. File NSMutableArray+SSToolkitAdditions.h contains shuffle method. You can use it also. Among this, there seem to be tons of useful things.

The main page of this library is here.

If you use this, your code will be like this:

#import <SSCategories.h>
NSMutableArray *tableData = [NSMutableArray arrayWithArray:[temp shuffledArray]];

This library also has a Pod (see CocoaPods)

Eirena

Answer 9

If elements have repeats.

e.g. array: A A A B B or B B A A A

only solution is: A B A B A

sequenceSelected is an NSMutableArray which stores elements of class obj, which are pointers to some sequence.

- (void)shuffleSequenceSelected {
    [sequenceSelected shuffle];
    [self shuffleSequenceSelectedLoop];
}

- (void)shuffleSequenceSelectedLoop {
    NSUInteger count = sequenceSelected.count;
    for (NSUInteger i = 1; i < count-1; i++) {
        // Select a random element between i and end of array to swap with.
        NSInteger nElements = count - i;
        NSInteger n;
        if (i < count-2) { // i is between second  and second last element
            obj *A = [sequenceSelected objectAtIndex:i-1];
            obj *B = [sequenceSelected objectAtIndex:i];
            if (A == B) { // shuffle if current & previous same
                do {
                    n = arc4random_uniform(nElements) + i;
                    B = [sequenceSelected objectAtIndex:n];
                } while (A == B);
                [sequenceSelected exchangeObjectAtIndex:i withObjectAtIndex:n];
            }
        } else if (i == count-2) { // second last value to be shuffled with last value
            obj *A = [sequenceSelected objectAtIndex:i-1];// previous value
            obj *B = [sequenceSelected objectAtIndex:i]; // second last value
            obj *C = [sequenceSelected lastObject]; // last value
            if (A == B && B == C) {
                //reshufle
                sequenceSelected = [[[sequenceSelected reverseObjectEnumerator] allObjects] mutableCopy];
                [self shuffleSequenceSelectedLoop];
                return;
            }
            if (A == B) {
                if (B != C) {
                    [sequenceSelected exchangeObjectAtIndex:i withObjectAtIndex:count-1];
                } else {
                    // reshuffle
                    sequenceSelected = [[[sequenceSelected reverseObjectEnumerator] allObjects] mutableCopy];
                    [self shuffleSequenceSelectedLoop];
                    return;
                }
            }
        }
    }
}

Accumbent

using a static prevents working on multiple instances: it would be much safer and readable to use two methods, a main one that does shuffle and calls the secondary method, while the secondary method only calls itself and never reshuffle. Also there is a spelling mistake. – Francis

App crash in this condition on "obj *C = [sequenceSelected lastObject]; " line if array contains only 3 element else if (i == count-2) { obj *A = [sequenceSelected objectAtIndex:i-1]; obj *B = [sequenceSelected objectAtIndex:i]; obj *C = [sequenceSelected lastObject]; if (A == B && B == C) { //reshufle sequenceSelected = [[[sequenceSelected reverseObjectEnumerator] allObjects] mutableCopy]; [self shuffleSequenceSelectedLoop]; return;} – Fungoid

Answer 10

NSUInteger randomIndex = arc4random() % [theArray count];

Biller

or arc4random_uniform([theArray count]) would be even better, if available on the version of Mac OS X or iOS you are supporting. – Saurian

I we given like this the number will repeat. – Coniah

Answer 11

Kristopher Johnson's answer is pretty nice, but it's not totally random.

Given an array of 2 elements, this function returns always the inversed array, because you are generating the range of your random over the rest of the indexes. A more accurate shuffle() function would be like

- (void)shuffle
{
   NSUInteger count = [self count];
   for (NSUInteger i = 0; i < count; ++i) {
       NSInteger exchangeIndex = arc4random_uniform(count);
       if (i != exchangeIndex) {
            [self exchangeObjectAtIndex:i withObjectAtIndex:exchangeIndex];
       }
   }
}

Carhop

I think the algorithm you've suggested is a "naive shuffle". See blog.codinghorror.com/the-danger-of-naivete. I think my answer has a 50% chance of swapping the elements if there are only two: when i is zero, arc4random_uniform(2) will return either 0 or 1, so the zeroth element will be either exchanged with itself or exchanged with the oneth element. On the next iteration, when i is 1, arc4random(1) will always return 0, and the ith element will always be exchanged with itself, which is inefficient but not incorrect. (Maybe the loop condition should be i < (count-1).) – Saurian

Answer 12

Edit: This is not correct. For reference purposes, I did not delete this post. See comments on the reason why this approach is not correct.

Simple code here:

- (NSArray *)shuffledArray:(NSArray *)array
{
    return [array sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
        if (arc4random() % 2) {
            return NSOrderedAscending;
        } else {
            return NSOrderedDescending;
        }
    }];
}

Renaissance

This shuffle is flawed – robweir.com/blog/2010/02/microsoft-random-browser-ballot.html – Francis