Если у вас NSMutableArray
, как вы перемешиваете элементы в случайном порядке?
(У меня есть собственный ответ, который опубликован ниже, но я новичок в Cocoa, и мне интересно узнать, есть ли лучший способ.)
Обновление: как отметил @Mukesh, начиная с iOS 10+ и macOS 10.12+, существует метод -[NSMutableArray shuffledArray]
, который можно использовать для перемешивания. Подробнее см. https://developer.apple.com/documentation/foundation/nsarray/1640855-shuffledarray?language=objc. (Но обратите внимание, что это создает новый массив, а не перемешивает элементы на месте.)
Взгляните на этот вопрос: Реальные проблемы с наивной перетасовкой относительно вашего алгоритма перетасовки.
На данный момент лучший вариант - Фишер-Йейтс: for (NSUInteger i = self.count; i > 1; i--) [self exchangeObjectAtIndex:i - 1 withObjectAtIndex:arc4random_uniform((u_int32_t)i)];
.
Ребят, из iOS 10 ++ новая концепция перетасовки массива предоставлено Apple, посмотрите этот ответ
Проблема с существующим API
заключается в том, что он возвращает новый Array
, который обращается к новому месту в памяти.
Я решил это, добавив категорию в NSMutableArray.
Редактировать: Удален ненужный метод благодаря ответу Ladd.
Редактировать: Изменен (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
Хорошее решение. И да, как упоминает willc2, замена random () на arc4random () - хорошее улучшение, поскольку не требуется никакого заполнения.
@Jason: Иногда (например, при тестировании) возможность предоставить семя - это хорошо. Кристофер: хороший алгоритм. Это реализация алгоритма Фишера-Йейтса: en.wikipedia.org/wiki/Fisher-Yates_shuffle
Обычно лучше использовать arc4random()
вместо random()
. Качество чисел на много лучше, раздача не требуется.
Улучшение супер минор: на последней итерации цикла i == count - 1. Разве это не означает, что мы обмениваем объект с индексом i с самим собой? Можем ли мы настроить код, чтобы всегда пропускать последнюю итерацию?
Я также добавил логическое значение «bool shuffled = false;» перед петлей. Во время цикла я проверяю «if (i! = N) shuffled = true;». И после цикла я проверяю, было ли перемешано: "if (! Shuffled) [self shuffle];" потому что у меня было много массивов с 3 элементами, которые не перемешивались регулярно.
@Thomas, есть только шесть способов заказать массив из трех элементов, так что можно ожидать, что примерно в 1/6 случаев все получится «без перетасовки». Если вы будете перетасовать каждый раз, когда это произойдет, результат не будет случайным.
Верно, но мои предметы всегда нужно перемешивать.
Считаете ли вы, что монета подбрасывается только в том случае, если результат противоположен той стороне, которая была изначально открыта?
Я предпочитаю использовать arc4random_uniform (nElements) вместо arc4random ()% nElements. Также используйте enumerateObjects вместо for. Пример: sourcedrop.net/Uyy787e411c71
Я использовал это, но как вызвать этот метод, я не нашел решения
Этот тасование слегка предвзято. Используйте arc4random_uniform(nElements)
вместо arc4random()%nElements
. См. страница руководства arc4random и это объяснение смещения по модулю для получения дополнительной информации.
Создать экземпляр NSInteger: s внутри цикла? Я бы не стал этого делать ... я всегда делаю const NSUInteger COUNT = [self count];
.
@Jonny NSInteger
- это просто typedef для int
или long
. «Создание» их не требует больших затрат, и компилятор, вероятно, их оптимизирует.
Не могли бы вы добавить предложение if, чтобы проверить, больше ли счетчик 0 или нет. Потому что, если массив пуст и он вызывается откуда-то, это вызовет проблему. также безопасная сторона проверки индекса обмена, выходит ли он за пределы массива или нет, а также является ли он отрицательным или нет.
@MaheshAgrawal Спасибо. Я добавил проверку на то, что количество меньше 1, что действительно вызовет проблемы. Я не думаю, что необходима дополнительная проверка индекса обмена, потому что он не может выходить за пределы из-за того, как он инициализирован.
@KristopherJohnson спасибо за добавление. и ты прав. на самом деле сначала, когда я отлаживал, он дал мне некоторые значения за пределами границ, но позже я понял, что это было из-за меньше нуля. Нет необходимости проверять выход за пределы, потому что вы уже добавили проверку.
@KristopherJohnson, последняя правка должна быть if (count <= 1) return;
? Зачем кому-то перемешивать массив с 1 элементом?
Вам не нужен метод swapObjectAtIndex. exchangeObjectAtIndex: withObjectAtIndex: уже существует.
Это самый простой и быстрый способ перемешать NSArrays или NSMutableArrays (объект puzzles - это 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 и решить, что вы хотите вернуть возможные значения:
Также для этого решения используйте arc4random () или seed.
Это перемешивание ошибочно - как недавно напомнили Microsoft: robweir.com/blog/2010/02/microsoft-random-browser-ballot.htm l.
Согласовано, ошибочно, потому что «сортировка требует самосогласованного определения порядка», как указано в той статье о MS. Выглядит элегантно, но на самом деле это не так.
NSUInteger randomIndex = arc4random() % [theArray count];
или arc4random_uniform([theArray count])
будет еще лучше, если он доступен в поддерживаемой вами версии Mac OS X или iOS.
Мы дали вот так число будет повторяться.
Поскольку я еще не могу комментировать, я подумал, что дам полный ответ. Я модифицировал реализацию Кристофера Джонсона для своего проекта несколькими способами (действительно стараясь сделать его как можно более кратким), одним из которых был 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
Обратите внимание, что вы вызываете [self count]
(средство получения свойства) дважды на каждой итерации цикла. Я думаю, что выведение его из цикла стоит потери лаконичности.
И поэтому я все еще предпочитаю [object method]
вместо object.method
: люди склонны забывать, что последнее не так дешево, как доступ к члену структуры, это связано с затратами на вызов метода ... очень плохо в цикле.
Спасибо за исправления - я ошибочно предположил, что счетчик по какой-то причине был кэширован. Обновил ответ.
Есть хорошая популярная библиотека, в состав которой входит этот метод, под названием SSToolKit в GitHub. Файл NSMutableArray + SSToolkitAdditions.h содержит метод перемешивания. Вы также можете использовать это. Среди этого вроде бы масса полезных вещей.
Главная страница этой библиотеки - здесь.
Если вы воспользуетесь этим, ваш код будет таким:
#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;
}
}
}
}
}
использование static
предотвращает работу с несколькими экземплярами: было бы намного безопаснее и удобнее использовать два метода: основной, который выполняет перемешивание и вызывает вторичный метод, в то время как вторичный метод вызывает только себя и никогда не перетасовывает. Также есть орфографическая ошибка.
Кристофер Джонсон ответ довольно приятный, но не совсем случайный.
Учитывая массив из 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];
}
}
}
Я думаю, что предложенный вами алгоритм - это «наивная перетасовка». См. blog.codinghorror.com/the-danger-of-naivete. Я думаю, что мой ответ имеет 50% шанс поменять местами элементы, если их всего два: когда i равно нулю, arc4random_uniform (2) вернет либо 0, либо 1, поэтому нулевой элемент будет либо обменен сам с собой, либо обменен с одним элемент. На следующей итерации, когда i равно 1, arc4random (1) всегда будет возвращать 0, а i-й элемент всегда будет заменен самим собой, что неэффективно, но не неверно. (Возможно, условие цикла должно быть i < (count-1)
.)
Edit: Это не так. Для справки я не удалял этот пост. См. Комментарии по поводу того, почему этот подход неверен.
Вот простой код:
- (NSArray *)shuffledArray:(NSArray *)array
{
return [array sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
if (arc4random() % 2) {
return NSOrderedAscending;
} else {
return NSOrderedDescending;
}
}];
}
Это перемешивание ошибочно - robweir.com/blog/2010/02/microsoft-random-browser-ballot.htm l
Немного улучшенное и краткое решение (по сравнению с лучшими ответами).
Алгоритм тот же, в литературе он описан как «Перемешивание Фишера-Йетса».
В 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
.
Примечание: Также доступен алгоритм нестабильного перемешивания (когда все позиции меняются, если count> 1).
В чем будет разница между этим и алгоритмом Кристофера Джонсона?
@IulianOnofrei, изначально код Кристофера Джонсона не был оптимальным, и я улучшил его ответ, затем его снова отредактировали с добавлением некоторой бесполезной начальной проверки. Я предпочитаю писать кратко. Алгоритм такой же и описан в литературе как «Перемешивание Фишера-Йетса».
Если вы импортируете GameplayKit
, есть shuffled
API:
https://developer.apple.com/reference/foundation/nsarray/1640855-shuffled
let shuffledArray = array.shuffled()
У меня есть myArray, и я хочу создать из него новый shuffleArray. Как мне это сделать с Objective-C?
shuffledArray = [array shuffledArray];
Обратите внимание, что этот метод является частью GameplayKit
, поэтому вам необходимо импортировать его.
Начиная с 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())
}
}
Вот реализация в Swift: iosdevelopertips.com/swift-code/swift-shuffle-array-type.htm l