什么是最好的方式来洗牌NSMutableArray?

如果你有一个NSMutableArray ,你如何随机地洗牌元素?

(我有我自己的答案,这是张贴在下面,但我是新cocoa,我很想知道如果有一个更好的办法。)


更新:正如@Mukesh所指出的,从iOS 10+和m​​acOS 10.12+开始,有一个可以用来洗牌的-[NSMutableArray shuffledArray]方法。 有关详细信息,请参阅https://developer.apple.com/documentation/foundation/nsarray/1640855-shuffledarray?language=objc 。 (但是请注意,这会创build一个新的数组,而不是将这些元素移动到位。)

您不需要swapObjectAtIndex方法。 exchangeObjectAtIndex:withObjectAtIndex:已经存在。

我通过向NSMutableArray添加一个类来解决这个问题。

编辑:删除不必要的方法感谢Ladd回答。

编辑:更改(arc4random() % nElements)arc4random_uniform(nElements)感谢格雷戈里Goltsov的答复和评论miho和blahdiblah

编辑:循环改进,感谢评论由罗恩

编辑:添加检查数组不是空的,由于评论由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 

由于我还没有评论,我想我会作出全面的回应。 我以许多方式修改了Kristopher Johnson的项目实现(尽量使其尽可能简洁),其中之一是arc4random_uniform()因为它避免了模数偏差 。

 // 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 

这是洗牌NSArrays或NSMutableArrays最简单和最快的方法(对象拼图是一个NSMutableArray,它包含拼图对象,我已经添加到拼图对象variables索引,它指示数组中的初始位置)

 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++; } } 

日志输出:

  #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 

你不妨将obj1和obj2进行比较,然后决定你想返回的值是:

  • NSOrderedAscending = -1
  • NSOrderedSame = 0
  • NSOrderedDescending = 1

从iOS 10开始,您可以使用新的shuffled API:

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

 let shuffledArray = array.shuffled() 

在编辑最佳答案之后,我想到分享一个稍微改进和简洁的解决scheme。

该algorithm是相同的,在文献中被描述为“ Fisher-Yates shuffle ”。

在ObjectiveC中:

 @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 

在Swift 3.2和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)))) } } } 

在Swift 3.0和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]) } } } 

注意: 使用GameplayKit可以在iOS10中使用更简洁的Swift解决scheme。

注意: 一个不稳定的混洗algorithm(如果count> 1,所有的位置都被强制改变)也是可用的

有一个很好的stream行的库,有这个方法,因为它的一部分, 在GitHub称为SSToolKit 。 文件NSMutableArray + SSToolkitAdditions.h包含shuffle方法。 你也可以使用它。 其中,似乎有很多有用的东西。

这个图书馆的主页在这里 。

如果你使用这个,你的代码将是这样的:

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

这个库也有一个Pod(见CocoaPods)

如果元素重复。

例如数组:AAABB或BBAAA

唯一的解决办法是:ABABA

sequenceSelected是一个存储类obj的元素的NSMutableArray,它是指向某个序列的指针。

 - (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; } } } } } 

从iOS 10开始,您可以使用GameplayKit中的NSArray shuffled() 。 这里是Swift 3中数组的助手:

 import GameplayKit extension Array { func shuffled() -> [Element] { return (self as NSArray).shuffled() as! [Element] } mutating func shuffle() { replaceSubrange(0..<count, with: shuffled()) } } 
 NSUInteger randomIndex = arc4random() % [theArray count]; 

克里斯托弗·约翰逊的回答非常好,但并不完全是随机的。

给定一个2个元素的数组,这个函数总是返回反向数组,因为你正在生成你的随机的范围在其余的索引。 一个更准确的shuffle()函数会是这样的

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

编辑: 这是不正确的。 为了便于参考,我没有删除这个post。 请参阅关于此方法不正确的原因的评论。

这里简单的代码:

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