Quelle est la meilleure façon de mélanger un NSMutableArray?

Si vous avez un NSMutableArray, comment mélangez-vous les éléments au hasard?

(J'ai ma propre réponse à ce sujet, qui est publiée ci-dessous, mais je suis nouveau sur Cocoa et je suis intéressé de savoir s'il existe un meilleur moyen.)

Mise à jour: comme indiqué par @Mukesh, à partir d'iOS 10+ et de macOS 10.12+, il existe une -[NSMutableArray shuffledArray]méthode qui peut être utilisée pour mélanger. Voir https://developer.apple.com/documentation/foundation/nsarray/1640855-shuffledarray?language=objc pour plus de détails. (Mais notez que cela crée un nouveau tableau, plutôt que de mélanger les éléments en place.)

Vous n'avez pas besoin de la méthode swapObjectAtIndex. exchangeObjectAtIndex: withObjectAtIndex: existe déjà.

J'ai résolu ce problème en ajoutant une catégorie à NSMutableArray.

Edit: Suppression de la méthode inutile grâce à la réponse de Ladd.

Edit: Changé (arc4random() % nElements)en arc4random_uniform(nElements)merci à la réponse de Gregory Goltsov et aux commentaires de miho et blahdiblah

Edit: Amélioration de la boucle, grâce au commentaire de Ron

Edit: Ajout de la vérification que le tableau n'est pas vide, grâce au commentaire de 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

Comme je ne peux pas encore commenter, j'ai pensé que je contribuerais à une réponse complète. J'ai modifié l'implémentation de Kristopher Johnson pour mon projet de plusieurs façons (en essayant vraiment de la rendre aussi concise que possible), l'une d'entre elles étant arc4random_uniform()parce qu'elle évite le biais modulo .

// 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

Si vous importez GameplayKit, il existe une shuffledAPI:

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

let shuffledArray = array.shuffled()

Une solution légèrement améliorée et concise (par rapport aux meilleures réponses).

L'algorithme est le même et est décrit dans la littérature sous le nom de " Fisher-Yates shuffle ".

En 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

Dans Swift 3.2 et 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))))
        }
    }
}

Dans Swift 3.0 et 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])
        }
    }
}

Remarque: Une solution plus concise dans Swift est possible à partir d'iOS10 en utilisant GameplayKit.

Remarque: Un algorithme de mélange instable (avec toutes les positions forcées de changer si nombre> 1) est également disponible

C'est le moyen le plus simple et le plus rapide de mélanger les NSArrays ou NSMutableArrays (les puzzles d'objets sont un NSMutableArray, il contient des objets de puzzle. J'ai ajouté à l'index de variable d'objet puzzle qui indique la position initiale dans le tableau)

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

sortie du journal:

 #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

vous pouvez également comparer obj1 avec obj2 et décider de ce que vous voulez renvoyer les valeurs possibles:

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

Il existe une belle bibliothèque populaire, qui comprend cette méthode, appelée SSToolKit dans GitHub . Le fichier NSMutableArray + SSToolkitAdditions.h contient la méthode shuffle. Vous pouvez également l'utiliser. Parmi cela, il semble y avoir des tonnes de choses utiles.

La page principale de cette bibliothèque est ici .

Si vous utilisez ceci, votre code sera comme ceci:

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

Cette bibliothèque possède également un Pod (voir CocoaPods)

À partir d'iOS 10, vous pouvez utiliser NSArray shuffled()depuis GameplayKit . Voici une aide pour Array dans 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())
    }
}

Si les éléments ont des répétitions.

par exemple, tableau: AAABB ou BBAAA

la seule solution est: ABEBA

sequenceSelected est un NSMutableArray qui stocke les éléments de la classe obj, qui sont des pointeurs vers une séquence.

- (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];

La réponse de Kristopher Johnson est plutôt sympa, mais ce n'est pas totalement aléatoire.

Étant donné un tableau de 2 éléments, cette fonction retourne toujours le tableau inversé, car vous générez la plage de votre aléatoire sur le reste des index. Une shuffle()fonction plus précise serait comme

- (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];
       }
   }
}

Edit: Ce n'est pas correct. À des fins de référence, je n'ai pas supprimé ce message. Voir les commentaires sur la raison pour laquelle cette approche n'est pas correcte.

Code simple ici:

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