Как лучше всего перемешать NSMutableArray?

Если у вас NSMutableArray, как вы перемешиваете элементы в случайном порядке?

(У меня есть собственный ответ, который опубликован ниже, но я новичок в Cocoa, и мне интересно узнать, есть ли лучший способ.)


Обновление: как отметил @Mukesh, начиная с iOS 10+ и macOS 10.12+, существует метод -[NSMutableArray shuffledArray], который можно использовать для перемешивания. Подробнее см. https://developer.apple.com/documentation/foundation/nsarray/1640855-shuffledarray?language=objc. (Но обратите внимание, что это создает новый массив, а не перемешивает элементы на месте.)

Вот реализация в Swift: iosdevelopertips.com/swift-code/swift-shuffle-array-type.htm‌ l

Kristopher Johnson 19.06.2014 23:02

Взгляните на этот вопрос: Реальные проблемы с наивной перетасовкой относительно вашего алгоритма перетасовки.

craigb 25.09.2008 21:31

На данный момент лучший вариант - Фишер-Йейтс: for (NSUInteger i = self.count; i > 1; i--) [self exchangeObjectAtIndex:i - 1 withObjectAtIndex:arc4random_uniform((u_int32_t)i)];.

Cœur 21.11.2015 10:14

Ребят, из iOS 10 ++ новая концепция перетасовки массива предоставлено Apple, посмотрите этот ответ

Mukesh 06.06.2017 10:21

Проблема с существующим API заключается в том, что он возвращает новый Array, который обращается к новому месту в памяти.

TheTiger 17.04.2018 14:22
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
191
5
77 357
12
Перейти к ответу Данный вопрос помечен как решенный

Ответы 12

Я решил это, добавив категорию в 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 Moore 12.01.2010 17:24

@Jason: Иногда (например, при тестировании) возможность предоставить семя - это хорошо. Кристофер: хороший алгоритм. Это реализация алгоритма Фишера-Йейтса: en.wikipedia.org/wiki/Fisher-Yates_shuffle

JeremyP 05.09.2011 15:28

Обычно лучше использовать arc4random() вместо random(). Качество чисел на много лучше, раздача не требуется.

zaph 15.01.2012 16:49

Улучшение супер минор: на последней итерации цикла i == count - 1. Разве это не означает, что мы обмениваем объект с индексом i с самим собой? Можем ли мы настроить код, чтобы всегда пропускать последнюю итерацию?

Ron 19.01.2012 23:49

Я также добавил логическое значение «bool shuffled = false;» перед петлей. Во время цикла я проверяю «if (i! = N) shuffled = true;». И после цикла я проверяю, было ли перемешано: "if (! Shuffled) [self shuffle];" потому что у меня было много массивов с 3 элементами, которые не перемешивались регулярно.

Thomas 18.10.2012 18:53

@Thomas, есть только шесть способов заказать массив из трех элементов, так что можно ожидать, что примерно в 1/6 случаев все получится «без перетасовки». Если вы будете перетасовать каждый раз, когда это произойдет, результат не будет случайным.

Kristopher Johnson 19.10.2012 09:33

Верно, но мои предметы всегда нужно перемешивать.

Thomas 19.10.2012 11:44

Считаете ли вы, что монета подбрасывается только в том случае, если результат противоположен той стороне, которая была изначально открыта?

Kristopher Johnson 22.10.2012 21:00

Я предпочитаю использовать arc4random_uniform (nElements) вместо arc4random ()% nElements. Также используйте enumerateObjects вместо for. Пример: sourcedrop.net/Uyy787e411c71

miho 05.11.2012 13:33

Я использовал это, но как вызвать этот метод, я не нашел решения

Jitendra 04.06.2013 11:55

Этот тасование слегка предвзято. Используйте arc4random_uniform(nElements) вместо arc4random()%nElements. См. страница руководства arc4random и это объяснение смещения по модулю для получения дополнительной информации.

blahdiblah 23.10.2013 05:07

Создать экземпляр NSInteger: s внутри цикла? Я бы не стал этого делать ... я всегда делаю const NSUInteger COUNT = [self count];.

Jonny 05.03.2015 06:10

@Jonny NSInteger - это просто typedef для int или long. «Создание» их не требует больших затрат, и компилятор, вероятно, их оптимизирует.

Kristopher Johnson 05.03.2015 19:05

Не могли бы вы добавить предложение if, чтобы проверить, больше ли счетчик 0 или нет. Потому что, если массив пуст и он вызывается откуда-то, это вызовет проблему. также безопасная сторона проверки индекса обмена, выходит ли он за пределы массива или нет, а также является ли он отрицательным или нет.

Mahesh Agrawal 18.01.2016 03:59

@MaheshAgrawal Спасибо. Я добавил проверку на то, что количество меньше 1, что действительно вызовет проблемы. Я не думаю, что необходима дополнительная проверка индекса обмена, потому что он не может выходить за пределы из-за того, как он инициализирован.

Kristopher Johnson 18.01.2016 19:15

@KristopherJohnson спасибо за добавление. и ты прав. на самом деле сначала, когда я отлаживал, он дал мне некоторые значения за пределами границ, но позже я понял, что это было из-за меньше нуля. Нет необходимости проверять выход за пределы, потому что вы уже добавили проверку.

Mahesh Agrawal 19.01.2016 05:26

@KristopherJohnson, последняя правка должна быть if (count <= 1) return;? Зачем кому-то перемешивать массив с 1 элементом?

Iulian Onofrei 19.08.2016 17:35
Ответ принят как подходящий

Вам не нужен метод 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 и решить, что вы хотите вернуть возможные значения:

  • NSOrderedAscending = -1
  • NSOrderedSame = 0
  • NSOrderedDescending = 1

Также для этого решения используйте arc4random () или seed.

Johan Kool 02.03.2010 03:38

Это перемешивание ошибочно - как недавно напомнили Microsoft: robweir.com/blog/2010/02/microsoft-random-browser-ballot.htm‌ l.

Raphael Schweikert 08.09.2010 18:19

Согласовано, ошибочно, потому что «сортировка требует самосогласованного определения порядка», как указано в той статье о MS. Выглядит элегантно, но на самом деле это не так.

Jeff 02.02.2013 01:32

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

или arc4random_uniform([theArray count]) будет еще лучше, если он доступен в поддерживаемой вами версии Mac OS X или iOS.

Kristopher Johnson 27.04.2012 02:38

Мы дали вот так число будет повторяться.

Vineesh TP 20.07.2012 08:42

Поскольку я еще не могу комментировать, я подумал, что дам полный ответ. Я модифицировал реализацию Кристофера Джонсона для своего проекта несколькими способами (действительно стараясь сделать его как можно более кратким), одним из которых был 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] (средство получения свойства) дважды на каждой итерации цикла. Я думаю, что выведение его из цикла стоит потери лаконичности.

Kristopher Johnson 22.10.2012 20:59

И поэтому я все еще предпочитаю [object method] вместо object.method: люди склонны забывать, что последнее не так дешево, как доступ к члену структуры, это связано с затратами на вызов метода ... очень плохо в цикле.

DarkDust 21.01.2013 18:34

Спасибо за исправления - я ошибочно предположил, что счетчик по какой-то причине был кэширован. Обновил ответ.

gregoltsov 25.03.2013 15:54

Есть хорошая популярная библиотека, в состав которой входит этот метод, под названием 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 предотвращает работу с несколькими экземплярами: было бы намного безопаснее и удобнее использовать два метода: основной, который выполняет перемешивание и вызывает вторичный метод, в то время как вторичный метод вызывает только себя и никогда не перетасовывает. Также есть орфографическая ошибка.

Cœur 30.06.2016 09:57

Кристофер Джонсон ответ довольно приятный, но не совсем случайный.

Учитывая массив из 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).)

Kristopher Johnson 16.10.2014 00:54

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

Cœur 14.07.2015 12:41

Немного улучшенное и краткое решение (по сравнению с лучшими ответами).

Алгоритм тот же, в литературе он описан как «Перемешивание Фишера-Йетса».

В 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).

В чем будет разница между этим и алгоритмом Кристофера Джонсона?

Iulian Onofrei 19.08.2016 17:37

@IulianOnofrei, изначально код Кристофера Джонсона не был оптимальным, и я улучшил его ответ, затем его снова отредактировали с добавлением некоторой бесполезной начальной проверки. Я предпочитаю писать кратко. Алгоритм такой же и описан в литературе как «Перемешивание Фишера-Йетса».

Cœur 22.08.2016 05:26

Если вы импортируете GameplayKit, есть shuffled API:

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

let shuffledArray = array.shuffled()

У меня есть myArray, и я хочу создать из него новый shuffleArray. Как мне это сделать с Objective-C?

Omkar Jadhav 04.12.2016 11:37

shuffledArray = [array shuffledArray];

andreacipriani 05.12.2016 18:02

Обратите внимание, что этот метод является частью GameplayKit, поэтому вам необходимо импортировать его.

AnthoPak 08.07.2019 16:35

Начиная с 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())
    }
}

Другие вопросы по теме