Как лучше всего перетасовать NSmutableArray?
-
09-06-2019 - |
Вопрос
Если у вас есть NSMutableArray
, как перетасовать элементы случайным образом?
(У меня есть собственный ответ на этот вопрос, который опубликован ниже, но я новичок в Какао, и мне интересно узнать, есть ли лучший способ.)
Обновлять:Как отметил @Mukesh, начиная с iOS 10+ и macOS 10.12+, существует -[NSMutableArray shuffledArray]
метод, который можно использовать для перетасовки.Видеть https://developer.apple.com/documentation/foundation/nsarray/1640855-shuffledarray?language=objc для получения подробной информации.(Но обратите внимание, что при этом создается новый массив, а не перетасовываются элементы.)
Решение
Вам не нужен метод swapObjectAtIndex. обменОбжектАтИндекс:withObjectAtIndex: уже существует.
Другие советы
Я решил эту проблему, добавив категорию в NSMutableArray.
Редактировать: Удален ненужный метод благодаря ответу Лэдда.
Редактировать: Измененный (arc4random() % nElements)
к arc4random_uniform(nElements)
спасибо за ответ Григория Гольцова и комментарии miho и blahdiblah
Редактировать: Улучшение цикла, благодаря комментарию Рона
Редактировать: Добавлена проверка того, что массив не пуст, благодаря комментарию Махеша Агравала.
// 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
.
Это самый простой и быстрый способ перетасовать 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 и решить, что вы хотите вернуть возможные значения:
- НСОдердедесцендинг = -1
- НСОрдедерсаме = 0
- НСОдердедесцендинг = 1
Существует хорошая популярная библиотека, в состав которой входит этот метод, называемый SSToolKit в GitHub.Файл NSMutableArray+SSToolkitAdditions.h содержит метод перемешивания.Вы также можете использовать его.Среди этого, кажется, есть масса полезных вещей.
Главная страница этой библиотеки: здесь.
Если вы используете это, ваш код будет таким:
#import <SSCategories.h>
NSMutableArray *tableData = [NSMutableArray arrayWithArray:[temp shuffledArray]];
В этой библиотеке также есть модуль (см. CocoaPods).
Начиная с iOS 10, вы можете использовать НСаррай 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())
}
}
Если элементы имеют повторы.
напримермножество:A A A B B или B B A A 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;
}
}
}
}
}
NSUInteger randomIndex = arc4random() % [theArray count];
Ответ Кристофера Джонсона это довольно приятно, но это не совсем случайно.
Учитывая массив из двух элементов, эта функция всегда возвращает инвертированный массив, поскольку вы генерируете диапазон случайных чисел по остальным индексам.Более точный 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;
}
}];
}