Jaki jest najlepszy sposób na przetasowanie tablicy NSMutableArray?

187

Jeśli masz NSMutableArray , jak losowo tasujesz elementy?

(Mam na to własną odpowiedź, która jest zamieszczona poniżej, ale jestem nowy w Cocoa i chcę wiedzieć, czy jest lepszy sposób).


Aktualizacja: Jak zauważył @Mukesh, od iOS 10+ i macOS 10.12+ istnieje -[NSMutableArray shuffledArray]metoda, której można użyć do losowego odtwarzania . Szczegółowe informacje można znaleźć na stronie https://developer.apple.com/documentation/foundation/nsarray/1640855-shuffledarray?language=objc . (Należy jednak pamiętać, że tworzy to nową tablicę zamiast tasowania elementów w miejscu).

Kristopher Johnson
źródło
Spójrz na to pytanie: rzeczywiste problemy z naiwnym tasowaniem w odniesieniu do algorytmu tasowania.
craigb
Oto implementacja w Swift: iosdevelopertips.com/swift-code/swift-shuffle-array-type.html
Kristopher Johnson
5
Obecnie najlepszy jest Fisher-Yates :for (NSUInteger i = self.count; i > 1; i--) [self exchangeObjectAtIndex:i - 1 withObjectAtIndex:arc4random_uniform((u_int32_t)i)];
Cœur
2
Chłopaki, z iOS 10 ++ nowa koncepcja tablicy losowej podana przez Apple, spójrz na tę odpowiedź
Mukesh
Problem z istniejącym APIpolega na tym, że zwraca nowy, Arrayktóry adresuje do nowej lokalizacji w pamięci.
TheTiger

Odpowiedzi:

349

Rozwiązałem to, dodając kategorię do NSMutableArray.

Edycja: Usunięto niepotrzebną metodę dzięki odpowiedzi Ladda.

Edytuj: zmieniono (arc4random() % nElements)naarc4random_uniform(nElements) dzięki dzięki odpowiedzi Gregory'ego Goltsova i komentarzom Miho i blahdiblaha

Edycja: Ulepszenie pętli dzięki komentarzowi Rona

Edycja: Dodano sprawdzenie, czy tablica nie jest pusta, dzięki komentarzowi Mahesha Agrawala

//  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
Kristopher Johnson
źródło
10
Niezłe rozwiązanie. I tak, jak wspomina willc2, zamiana random () na arc4random () jest niezłą poprawą, ponieważ nie jest wymagane seedowanie.
Jason Moore,
4
@Jason: Czasami (np. Podczas testowania) możliwość dostarczenia nasion jest dobrą rzeczą. Kristopher: niezły algorytm. Jest to implementacja algorytmu Fisher-Yates: en.wikipedia.org/wiki/Fisher-Yates_shuffle
JeremyP
4
Bardzo drobna poprawa: w ostatniej iteracji pętli i == count - 1. Czy to nie znaczy, że wymieniamy obiekt o indeksie i ze sobą? Czy możemy dostosować kod, aby zawsze pomijał ostatnią iterację?
Ron
10
Czy uważasz, że monetę można rzucić tylko wtedy, gdy wynik jest przeciwny do tej, która była pierwotnie podniesiona?
Kristopher Johnson
4
Ten los jest subtelnie tendencyjny. Użyj arc4random_uniform(nElements)zamiast arc4random()%nElements. Aby uzyskać więcej informacji, zobacz stronę podręcznika użytkownika arc4random i wyjaśnienie błędu modulo .
blahdiblah
38

Ponieważ nie mogę jeszcze komentować, pomyślałem, że udzielę pełnej odpowiedzi. Zmodyfikowałem implementację Kristophera Johnsona dla mojego projektu na wiele sposobów (naprawdę starając się, aby była jak najbardziej zwięzła), jednym z nich jest arc4random_uniform()to, że unika modulo stronniczości .

// 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
Gregoltsov
źródło
2
Zauważ, że wywołujesz [self count](getter właściwości) dwa razy podczas każdej iteracji przez pętlę. Myślę, że wyprowadzenie go z pętli jest warte utraty zwięzłości.
Kristopher Johnson
1
I dlatego nadal wolę [object method]zamiast object.method: ludzie zapominają, że później nie jest tak tanie, jak dostęp do członka struktury, wiąże się to z kosztem wywołania metody ... bardzo źle w pętli.
DarkDust
Dziękuję za poprawki - z jakiegoś powodu błędnie założyłem, że liczba została zapisana w pamięci podręcznej. Zaktualizowałem odpowiedź.
gregoltsov,
10

Jeśli zaimportujesz GameplayKit, istnieje shuffledinterfejs API:

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

let shuffledArray = array.shuffled()
andreacipriani
źródło
Mam myArray i chcę go utworzyć. Jak to zrobić za pomocą Celu - C?
Omkar Jadhav,
shuffledArray = [array shuffledArray];
andreacipriani,
Pamiętaj, że ta metoda jest częścią, GameplayKitwięc musisz ją zaimportować.
AnthoPak,
9

Nieco ulepszone i zwięzłe rozwiązanie (w porównaniu do najlepszych odpowiedzi).

Algorytm jest taki sam i jest opisany w literaturze jako „ Shuffle Fishera-Yatesa ”.

W celu 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

W Swift 3.2 i 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))))
        }
    }
}

W Swift 3.0 i 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])
        }
    }
}

Uwaga: Bardziej zwięzłe rozwiązanie w Swift jest możliwe z iOS10 przy użyciu GameplayKit.

Uwaga: Dostępny jest również algorytm niestabilnego tasowania (ze wszystkimi pozycjami zmuszonymi do zmiany, jeśli liczba> 1)

Cœur
źródło
Jaka byłaby różnica między tym a algorytmem Kristophera Johnsona?
Iulian Onofrei,
@IulianOnofrei, początkowo kod Kristophera Johnsona nie był optymalny i poprawiłem jego odpowiedź, a następnie ponownie go edytowałem z dodaniem niepotrzebnego wstępnego sprawdzania. Wolę mój zwięzły sposób pisania. Algorytm jest taki sam i jest opisany w literaturze jako „ Shuffle Fishera-Yatesa ”.
Cœur
6

Jest to najprostszy i najszybszy sposób przetasowania tablic NSArrays lub NSMutableArrays (puzzle obiektowe to NSMutableArray, zawiera obiekty logiczne. Dodałem do indeksu zmiennych obiektu logicznego, który wskazuje początkową pozycję w tablicy)

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

dane wyjściowe dziennika:

 #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

równie dobrze możesz porównać obj1 z obj2 i zdecydować, jakie wartości chcesz zwrócić:

  • NSOrdersAscending = -1
  • NSOrdersSame = 0
  • NSOrdersDescending = 1

źródło
1
Również dla tego rozwiązania użyj arc4random () lub seed.
Johan Kool
17
Ten los jest wadliwy - jak ostatnio przypomniano Microsoft: robweir.com/blog/2010/02/microsoft-random-browser-ballot.html .
Raphael Schweikert
Uzgodniony, wadliwy, ponieważ „sortowanie wymaga spójnej definicji porządku”, jak wskazano w tym artykule o stwardnieniu rozsianym. Wygląda elegancko, ale nie jest.
Jeff
2

Istnieje dobra popularna biblioteka, która ma tę metodę jako część, o nazwie SSToolKit w GitHub . Plik NSMutableArray + SSToolkitAdditions.h zawiera metodę losową. Możesz go również użyć. Wśród nich wydaje się, że jest mnóstwo przydatnych rzeczy.

Strona główna tej biblioteki jest tutaj .

Jeśli tego użyjesz, twój kod będzie wyglądał następująco:

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

Ta biblioteka ma również kapsułę (patrz CocoaPods)

Denis Kutlubaev
źródło
2

W iOS 10 możesz używać NSArray shuffled()z GameplayKit . Oto pomocnik dla Array w 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())
    }
}
Cœur
źródło
1

Jeśli elementy mają powtórzenia.

np. tablica: AAABB lub BBAAA

jedynym rozwiązaniem jest: ABABA

sequenceSelected jest NSMutableArray, który przechowuje elementy klasy obj, które są wskaźnikami do jakiejś sekwencji.

- (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;
                }
            }
        }
    }
}
Punkt gamma
źródło
użycie a staticzapobiega pracy w wielu instancjach: byłoby znacznie bezpieczniej i czytelniej korzystać z dwóch metod, głównej, która tasuje i wywołuje metodę drugorzędną, podczas gdy metoda wtórna wywołuje samą siebie i nigdy nie przetasowuje. Jest też błąd ortograficzny.
Cœur
-1
NSUInteger randomIndex = arc4random() % [theArray count];
kal
źródło
2
lub arc4random_uniform([theArray count])byłoby jeszcze lepiej, jeśli jest dostępna w obsługiwanej wersji Mac OS X lub iOS.
Kristopher Johnson
1
Podaliśmy w ten sposób, że liczba się powtórzy.
Vineesh TP,
-1

Odpowiedź Kristophera Johnsona jest całkiem ładna, ale nie jest całkowicie losowa.

Biorąc pod uwagę tablicę 2 elementów, funkcja ta zawsze zwraca tablicę odwróconą, ponieważ generujesz zakres swojej losowości na pozostałych indeksach. shuffle()Byłaby bardziej dokładna funkcja

- (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];
       }
   }
}
fcortes
źródło
Myślę, że algorytm, który zasugerowałeś, jest „naiwnym tasowaniem”. Zobacz blog.codinghorror.com/the-danger-of-naivete . Myślę, że moja odpowiedź ma 50% szansy na zamianę elementów, jeśli są tylko dwa: gdy i wynosi zero, arc4random_uniform (2) zwróci 0 lub 1, więc element zerowy zostanie albo wymieniony na siebie, albo na oneth element. Przy następnej iteracji, gdy i ma wartość 1, funkcja arc4random (1) zawsze zwraca wartość 0, a i-ty element zawsze będzie wymieniany z samym sobą, co jest nieefektywne, ale nie jest nieprawidłowe. (Może warunek pętli powinien być i < (count-1).)
Kristopher Johnson
-2

Edycja: Niepoprawne.W celach informacyjnych nie usunąłem tego postu. Zobacz komentarze na temat powodów, dla których to podejście jest nieprawidłowe.

Prosty kod tutaj:

- (NSArray *)shuffledArray:(NSArray *)array
{
    return [array sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
        if (arc4random() % 2) {
            return NSOrderedAscending;
        } else {
            return NSOrderedDescending;
        }
    }];
}
Ultimate Pea
źródło