什么是洗牌NSMutableArray的最佳方式？

如果你有NSMutableArray,你如何随机洗牌？

(我有自己的答案,发布在下面,但我是Cocoa的新手,我很想知道是否有更好的方法.)

---

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

1> Kristopher J..：

---

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

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

编辑:更改(arc4random() % nElements)到arc4random_uniform(nElements)要归功于美穗和blahdiblah由格雷戈里Goltsov和评论回答

编辑:循环改进,感谢Ron的评论

编辑:由于Mahesh Agrawal的评论,已添加检查数组是否为空

//  NSMutableArray_Shuffling.h

#if TARGET_OS_IPHONE
#import 
#else
#include 
#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

---

好的解决方案 是的,正如willc2所提到的,用arc4random()替换random()是一个很好的改进,因为不需要播种.

---

你是否认为只有当结果与最初的一侧相反时才能翻转硬币？

---

@Jason:有时(例如在测试时),能够提供种子是一件好事.克里斯托弗:不错的算法.这是Fisher-Yates算法的一个实现:http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

---

一个**超小**改进:在循环的最后一次迭代中,i == count - 1.这是不是意味着我们在索引i处交​​换对象本身？我们可以调整代码以始终跳过最后一次迭代吗？

---

这种洗牌有微妙的偏见.使用`arc4random_uniform(nElements)`而不是`arc4random()%nElements`.参见[arc4random手册页](https://developer.apple.com/library/mac/documentation/Darwin/Reference/ManPages/man3/arc4random_uniform.3.html)和[modulo bias的这种解释](http:/ /stackoverflow.com/q/10984974/85950)了解更多信息.

2> 小智..：

---

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

3> gregoltsov..：

---

由于我还不能发表评论,我想我会做出全面回应.我以多种方式修改了Kristopher Johnson对我项目的实现(真的试图让它尽可能简洁),其中之一是arc4random_uniform()因为它避免了模数偏差.

// NSMutableArray+Shuffling.h
#import 

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

---

请注意,在循环的每次迭代中,您都会调用两次"[self count]"(属性获取器).我认为将它移出循环是值得失去简洁的.

4> Cœur..：

---

一个略微改进和简洁的解决方案(与最佳答案相比).

算法是相同的,并在文献中描述为" Fisher-Yates shuffle ".

在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

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

注意:使用iOS10可以在Swift中使用更简洁的解决方案GameplayKit.

注意:也可以使用不稳定混洗的算法(如果count> 1,所有位置都被强制改变)

5> andreacipria..：

---

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

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

let shuffledArray = array.shuffled()

6> 小智..：

---

这是改组NSArrays或NSMutableArrays的最简单,最快捷的方法(对象谜题是NSMutableArray,它包含谜题对象.我已添加到谜题对象变量索引,表示数组中的初始位置)

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

---

这种洗牌是有缺陷的 - 正如微软最近提醒过的那样:http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html.