Какой лучший способ перемешать массив NSMutableArray?
Если у вас есть NSMutableArrayКак вы случайным образом перемешаете элементы?
(У меня есть собственный ответ на этот вопрос, который опубликован ниже, но я новичок в Какао, и мне интересно знать, есть ли лучший способ.)
Обновление: как отмечает @Mukesh, в iOS 10+ и macOS 10.12+ существует -[NSMutableArray shuffledArray] метод, который может быть использован для перемешивания. Подробнее см. https://developer.apple.com/documentation/foundation/nsarray/1640855-shuffledarray?language=objc. (Но обратите внимание, что это создает новый массив, а не перетасовывает элементы на месте.)
12 ответов
Вам не нужен метод swapObjectAtIndex. exchangeObjectAtIndex: withObjectAtIndex: уже существует.
Я решил это, добавив категорию в NSMutableArray.
Изменить: Удален ненужный метод благодаря ответу Лэдд.
Изменить: Изменено (arc4random() % nElements) в arc4random_uniform(nElements) благодаря ответу Григория Гольцова и комментариям Михо и Бладиблы
Изменить: улучшение петли, благодаря комментарию Рона
Редактировать: добавлена проверка, что массив не пуст, благодаря комментарию Махеш Агравал
// 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
Поскольку я пока не могу комментировать, я подумала, что внесу полный ответ. Я изменил реализацию Кристофера Джонсона для своего проекта несколькими способами (действительно пытаясь сделать его как можно более кратким), одним из которых был 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
С iOS 10 вы можете использовать новый shuffled API:
https://developer.apple.com/reference/foundation/nsarray/1640855-shuffled
let shuffledArray = array.shuffled()
Немного улучшенное и краткое решение (по сравнению с основными ответами).
Алгоритм такой же и описан в литературе как " случай Фишера-Йейтса ".
В 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).
Это самый простой и быстрый способ перемешать 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
С iOS 10 вы можете использовать NSArray shuffled() из GameplayKit. Вот помощник для Array в 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())
}
}
Существует хорошая популярная библиотека, в которой этот метод входит в состав SSToolKit в GitHub. Файл NSMutableArray+SSToolkitAdditions.h содержит метод shuffle. Вы можете использовать это также. Среди этого, кажется, есть тонны полезных вещей.
Главная страница этой библиотеки находится здесь.
Если вы используете это, ваш код будет выглядеть так:
#import <SSCategories.h>
NSMutableArray *tableData = [NSMutableArray arrayWithArray:[temp shuffledArray]];
Эта библиотека также имеет Pod (см. CocoaPods)
Если элементы повторяются.
например, массив: A A A B B или B B A A A
Единственное решение: A B A B A
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;
}
}
}
}
}
Ответ Кристофера Джонсона довольно приятный, но не совсем случайный.
Учитывая массив из 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];
}
}
}
Редактировать: это не правильно. Для справки я не удалил этот пост. Смотрите комментарии о причине, почему этот подход не является правильным.
Простой код здесь:
- (NSArray *)shuffledArray:(NSArray *)array
{
return [array sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
if (arc4random() % 2) {
return NSOrderedAscending;
} else {
return NSOrderedDescending;
}
}];
}