objective-c - 洗牌 NSMutableArray 的最佳方法是什么？

Question

如果你有一个NSMutableArray，你如何随机打乱元素？

（我对此有自己的答案，发布在下面，但我是 Cocoa 的新手，我很想知道是否有更好的方法。）

更新：正如@Mukesh 所指出的，从 iOS 10+ 和 macOS 10.12+ 开始，有一种-[NSMutableArray shuffledArray]方法可用于随机播放。有关详细信息，请参阅https://developer.apple.com/documentation/foundation/nsarray/1640855-shuffledarray?language=objc。（但请注意，这会创建一个新数组，而不是在原地打乱元素。）

score 352 · Accepted Answer

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

编辑：由于 Ladd 的回答，删除了不必要的方法。

编辑：更改(arc4random() % nElements)为arc4random_uniform(nElements)感谢 Gregory Goltsov 的回答以及 miho 和 blahdiblah 的评论

编辑：循环改进，感谢 Ron 的评论

编辑：添加检查数组不为空，感谢 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

score 74 · Accepted Answer

74

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

于 2008-09-11T21:03:24.333 回答

score 39 · Accepted Answer

由于我还不能发表评论，我想我会做出一个完整的回应。我以多种方式修改了 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

score 12 · Accepted Answer

如果你 import GameplayKit，有一个shuffledAPI：

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

let shuffledArray = array.shuffled()

score 11 · Accepted Answer

稍微改进和简洁的解决方案（与最佳答案相比）。

该算法是相同的并且在文献中被描述为“ 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])
        }
    }
}

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

注意：不稳定洗牌的算法（如果计数> 1，所有位置都强制改变）也可用

score 6 · Accepted Answer

这是洗牌 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

score 3 · Accepted Answer

从 iOS 10 开始，您可以使用GameplayKit中的 NSArrayshuffled()。这是 Swift 3 中 Array 的帮助器：

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

score 2 · Accepted Answer

有一个不错的流行库，其中包含此方法，在 GitHub 中称为SSToolKit。文件 NSMutableArray+SSToolkitAdditions.h 包含 shuffle 方法。你也可以使用它。其中，似乎有很多有用的东西。

这个库的主页在这里。

如果你使用它，你的代码将是这样的：

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

这个库也有一个 Pod（参见 CocoaPods）

score 1 · Accepted Answer

如果元素有重复。

例如数组：AAABB 或 BBAAA

唯一的解决方案是：ABABA

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

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

score -1 · Accepted Answer

-1

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

于 2012-04-26T13:42:45.977 回答

score -1 · Accepted Answer

Kristopher Johnson 的回答非常好，但并非完全随机。

给定一个包含 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];
       }
   }
}

score -2 · Accepted Answer

编辑：这是不正确的。出于参考目的，我没有删除此帖子。请参阅有关此方法不正确原因的评论。

这里的简单代码：

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

objective-c - 洗牌 NSMutableArray 的最佳方法是什么？

12 回答 12

Related

Reference