Was ist der beste Weg, um ein NSMutableArray zu mischen?

187

Wenn Sie eine haben NSMutableArray, wie mischen Sie die Elemente zufällig?

(Ich habe meine eigene Antwort darauf, die unten veröffentlicht ist, aber ich bin neu bei Cocoa und ich bin interessiert zu wissen, ob es einen besseren Weg gibt.)


Update: Wie von @Mukesh festgestellt, gibt es ab iOS 10+ und macOS 10.12+ eine -[NSMutableArray shuffledArray]Methode, die zum Mischen verwendet werden kann. Weitere Informationen finden Sie unter https://developer.apple.com/documentation/foundation/nsarray/1640855-shuffledarray?language=objc . (Beachten Sie jedoch, dass dadurch ein neues Array erstellt wird, anstatt die vorhandenen Elemente zu mischen.)

Kristopher Johnson
quelle
Schauen Sie sich diese Frage an: Reale Probleme mit naivem Mischen in Bezug auf Ihren Mischalgorithmus.
Craigb
Hier ist eine Implementierung in Swift: iosdevelopertips.com/swift-code/swift-shuffle-array-type.html
Kristopher Johnson
5
Derzeit am besten ist Fisher-Yates :for (NSUInteger i = self.count; i > 1; i--) [self exchangeObjectAtIndex:i - 1 withObjectAtIndex:arc4random_uniform((u_int32_t)i)];
Cœur
2
Leute, von iOS 10 ++ neues Konzept des Shuffle-Arrays von Apple, Schauen Sie sich diese Antwort an
Mukesh
Das Problem mit dem vorhandenen APIist, dass es eine neue ArrayAdresse zurückgibt, die an einen neuen Speicherort im Speicher adressiert.
TheTiger

Antworten:

349

Ich habe dieses Problem gelöst, indem ich NSMutableArray eine Kategorie hinzugefügt habe.

Bearbeiten: Unnötige Methode dank Antwort von Ladd entfernt.

Bearbeiten: Geändert (arc4random() % nElements)zu arc4random_uniform(nElements)Dank der Antwort von Gregory Goltsov und Kommentaren von Miho und Blahdiblah

Edit: Loop-Verbesserung dank Kommentar von Ron

Bearbeiten: Es wurde hinzugefügt, dass das Array nicht leer ist, dank des Kommentars von Mahesh Agrawal

//  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
quelle
10
Schöne Lösung. Und ja, wie willc2 erwähnt, ist das Ersetzen von random () durch arc4random () eine nette Verbesserung, da kein Seeding erforderlich ist.
Jason Moore
4
@ Jason: Manchmal (zB beim Testen) ist es eine gute Sache, einen Samen liefern zu können. Kristopher: netter Algorithmus. Es ist eine Implementierung des Fisher-Yates-Algorithmus: en.wikipedia.org/wiki/Fisher-Yates_shuffle
JeremyP
4
Eine super kleine Verbesserung: In der letzten Iteration der Schleife ist i == count - 1. Bedeutet das nicht, dass wir das Objekt am Index i mit sich selbst austauschen? Können wir den Code optimieren, um immer die letzte Iteration zu überspringen?
Ron
10
Betrachten Sie eine Münze nur dann als geworfen, wenn das Ergebnis das Gegenteil der Seite ist, die ursprünglich oben war?
Kristopher Johnson
4
Dieses Mischen ist subtil voreingenommen. Verwenden Sie arc4random_uniform(nElements)anstelle von arc4random()%nElements. Weitere Informationen finden Sie in der Manpage arc4random und in dieser Erklärung zu Modulo Bias .
Blahdiblah
38

Da ich noch keinen Kommentar abgeben kann, dachte ich, ich würde eine vollständige Antwort beisteuern. Ich habe die Implementierung von Kristopher Johnson für mein Projekt auf verschiedene Weise modifiziert (wirklich versucht, es so präzise wie möglich zu gestalten), unter anderem, arc4random_uniform()weil dadurch Modulo-Bias vermieden werden .

// 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
quelle
2
Beachten Sie, dass Sie [self count]bei jeder Iteration durch die Schleife zweimal (einen Eigenschafts-Getter) aufrufen . Ich denke, es ist den Verlust der Prägnanz wert, es aus der Schleife zu entfernen.
Kristopher Johnson
1
Und deshalb bevorzuge ich immer noch, [object method]anstatt object.method: Die Leute neigen dazu zu vergessen, dass letzteres nicht so billig ist wie der Zugriff auf ein Strukturelement, sondern mit den Kosten eines Methodenaufrufs verbunden ist ... sehr schlecht in einer Schleife.
DarkDust
Vielen Dank für die Korrekturen. Ich habe fälschlicherweise angenommen, dass die Zählung aus irgendeinem Grund zwischengespeichert wurde. Die Antwort wurde aktualisiert.
Gregoltsov
10

Wenn Sie importieren GameplayKit, gibt es eine shuffledAPI:

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

let shuffledArray = array.shuffled()
andreacipriani
quelle
Ich habe myArray und möchte ein neues ShuffleArray davon erstellen. Wie mache ich das mit Objective - C?
Omkar Jadhav
shuffledArray = [array shuffledArray];
andreacipriani
Beachten Sie, dass diese Methode Teil von ist, GameplayKitsodass Sie sie importieren müssen.
AnthoPak
9

Eine leicht verbesserte und prägnante Lösung (im Vergleich zu den Top-Antworten).

Der Algorithmus ist der gleiche und wird in der Literatur als " Fisher-Yates-Shuffle " beschrieben.

In Ziel-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

In Swift 3.2 und 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))))
        }
    }
}

In Swift 3.0 und 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])
        }
    }
}

Hinweis: Eine präzisere Lösung in Swift ist ab iOS10 mit möglich GameplayKit.

Hinweis: Ein Algorithmus für instabiles Mischen (bei dem alle Positionen geändert werden müssen, wenn die Anzahl> 1 ist) ist ebenfalls verfügbar

Cœur
quelle
Was wäre der Unterschied zwischen diesem und Kristopher Johnsons Algorithmus?
Iulian Onofrei
@IulianOnofrei, ursprünglich war Kristopher Johnsons Code nicht optimal und ich habe seine Antwort verbessert, dann wurde er erneut bearbeitet, wobei einige nutzlose erste Überprüfungen hinzugefügt wurden. Ich bevorzuge meine prägnante Schreibweise. Der Algorithmus ist der gleiche und wird in der Literatur als " Fisher-Yates-Shuffle " beschrieben.
Cœur
6

Dies ist der einfachste und schnellste Weg, um NSArrays oder NSMutableArrays zu mischen (Objektpuzzles sind ein NSMutableArray, es enthält Puzzleobjekte. Ich habe den Index der Puzzleobjektvariablen hinzugefügt, der die Anfangsposition im Array angibt.)

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

Protokollausgabe:

 #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

Sie können auch obj1 mit obj2 vergleichen und entscheiden, welche möglichen Werte Sie zurückgeben möchten:

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

quelle
1
Verwenden Sie für diese Lösung auch arc4random () oder seed.
Johan Kool
17
Dieses Shuffle ist fehlerhaft - wie Microsoft kürzlich erinnert wurde: robweir.com/blog/2010/02/microsoft-random-browser-ballot.html .
Raphael Schweikert
Einverstanden, fehlerhaft, weil "das Sortieren eine selbstkonsistente Definition der Reihenfolge erfordert", wie in diesem Artikel über MS ausgeführt. Sieht elegant aus, ist es aber nicht.
Jeff
2

Es gibt eine nette, beliebte Bibliothek, die diese Methode als Teil hat und SSToolKit in GitHub heißt . Die Datei NSMutableArray + SSToolkitAdditions.h enthält die Shuffle-Methode. Sie können es auch verwenden. Unter diesen scheint es Unmengen nützlicher Dinge zu geben.

Die Hauptseite dieser Bibliothek ist hier .

Wenn Sie dies verwenden, sieht Ihr Code folgendermaßen aus:

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

Diese Bibliothek hat auch einen Pod (siehe CocoaPods)

Denis Kutlubaev
quelle
2

Ab iOS 10 können Sie NSArray shuffled()von GameplayKit aus verwenden . Hier ist ein Helfer für Array in 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
quelle
1

Wenn Elemente Wiederholungen haben.

zB Array: AAABB oder BBAAA

einzige Lösung ist: ABABA

sequenceSelected ist ein NSMutableArray, das Elemente der Klasse obj speichert, die Zeiger auf eine Sequenz sind.

- (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;
                }
            }
        }
    }
}
Gammapunkt
quelle
Die Verwendung von a staticverhindert das Arbeiten an mehreren Instanzen: Es wäre viel sicherer und lesbarer, zwei Methoden zu verwenden, eine Hauptmethode, die die sekundäre Methode mischt und aufruft, während die sekundäre Methode nur sich selbst aufruft und niemals neu mischt. Es gibt auch einen Rechtschreibfehler.
Cœur
-1
NSUInteger randomIndex = arc4random() % [theArray count];
kal
quelle
2
oder arc4random_uniform([theArray count])wäre sogar noch besser, wenn es auf der von Ihnen unterstützten Version von Mac OS X oder iOS verfügbar ist.
Kristopher Johnson
1
Wenn wir so gegeben haben, wird sich die Nummer wiederholen.
Vineesh TP
-1

Kristopher Johnsons Antwort ist ziemlich nett, aber nicht völlig zufällig.

Bei einem Array mit 2 Elementen gibt diese Funktion immer das inverse Array zurück, da Sie den Bereich Ihres Zufalls über den Rest der Indizes generieren. Eine genauere shuffle()Funktion wäre wie

- (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
quelle
Ich denke, der Algorithmus, den Sie vorgeschlagen haben, ist ein "naives Mischen". Siehe blog.codinghorror.com/the-danger-of-naivete . Ich denke, meine Antwort hat eine 50% ige Chance, die Elemente zu tauschen, wenn es nur zwei gibt: Wenn i Null ist, gibt arc4random_uniform (2) entweder 0 oder 1 zurück, sodass das nullte Element entweder mit sich selbst oder mit dem einen ausgetauscht wird Element. Bei der nächsten Iteration, wenn i 1 ist, gibt arc4random (1) immer 0 zurück, und das i-te Element wird immer mit sich selbst ausgetauscht, was ineffizient, aber nicht falsch ist. (Vielleicht sollte die Schleifenbedingung sein i < (count-1).)
Kristopher Johnson
-2

Bearbeiten: Dies ist nicht korrekt. Zu Referenzzwecken habe ich diesen Beitrag nicht gelöscht. Siehe Kommentare zum Grund, warum dieser Ansatz nicht korrekt ist.

Einfacher Code hier:

- (NSArray *)shuffledArray:(NSArray *)array
{
    return [array sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
        if (arc4random() % 2) {
            return NSOrderedAscending;
        } else {
            return NSOrderedDescending;
        }
    }];
}
Ultimative Erbse
quelle