¿Cuál es la mejor manera de barajar una matriz NSMutableArray?

187

Si tienes un NSMutableArray, ¿cómo barajas los elementos al azar?

(Tengo mi propia respuesta para esto, que se publica a continuación, pero soy nuevo en Cocoa y estoy interesado en saber si hay una mejor manera).


Actualización: Como señaló @Mukesh, a partir de iOS 10+ y macOS 10.12+, hay un -[NSMutableArray shuffledArray]método que puede usarse para barajar. Consulte https://developer.apple.com/documentation/foundation/nsarray/1640855-shuffledarray?language=objc para más detalles. (Pero tenga en cuenta que esto crea una nueva matriz, en lugar de barajar los elementos en su lugar).

Kristopher Johnson
fuente
Eche un vistazo a esta pregunta: problemas del mundo real con barajado ingenuo con respecto a su algoritmo de barajado.
craigb
Aquí hay una implementación en Swift: iosdevelopertips.com/swift-code/swift-shuffle-array-type.html
Kristopher Johnson
55
El mejor actual es Fisher-Yates :for (NSUInteger i = self.count; i > 1; i--) [self exchangeObjectAtIndex:i - 1 withObjectAtIndex:arc4random_uniform((u_int32_t)i)];
Cœur
2
Chicos, desde iOS 10 ++ nuevo concepto de matriz aleatoria dado por Apple, miren esta respuesta
Mukesh
El problema con existente APIes que devuelve un nuevo Arrayque se dirige a una nueva ubicación en la memoria.
TheTiger

Respuestas:

349

Resolví esto agregando una categoría a NSMutableArray.

Editar: Se eliminó el método innecesario gracias a la respuesta de Ladd.

Editar: cambiado (arc4random() % nElements)a arc4random_uniform(nElements)gracias a la respuesta de Gregory Goltsov y los comentarios de miho y blahdiblah

Editar: Mejora de bucle, gracias al comentario de Ron

Editar: se agregó la verificación de que la matriz no está vacía, gracias al comentario 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
Kristopher Johnson
fuente
10
Buena solución Y sí, como menciona willc2, reemplazar random () con arc4random () es una buena mejora, ya que no se requiere la inicialización.
Jason Moore
44
@ Jason: A veces (por ejemplo, durante las pruebas), poder suministrar una semilla es algo bueno. Kristopher: buen algoritmo. Es una implementación del algoritmo Fisher-Yates: en.wikipedia.org/wiki/Fisher-Yates_shuffle
JeremyP
44
Una mejora súper menor : en la última iteración del ciclo, i == count - 1. ¿No significa eso que estamos intercambiando el objeto en el índice i consigo mismo? ¿Podemos modificar el código para omitir siempre la última iteración?
Ron
10
¿Considera que una moneda se voltea solo si el resultado es el opuesto del lado que originalmente estaba arriba?
Kristopher Johnson
44
Este shuffle está sutilmente sesgado. Usar en arc4random_uniform(nElements)lugar de arc4random()%nElements. Consulte la página de manual arc4random y esta explicación del sesgo de módulo para obtener más información.
blahdiblah
38

Como todavía no puedo comentar, pensé que contribuiría con una respuesta completa. Modifiqué la implementación de Kristopher Johnson para mi proyecto de varias maneras (realmente tratando de hacerlo lo más conciso posible), una de ellas es arc4random_uniform()porque evita el sesgo de módulo .

// 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
fuente
2
Tenga en cuenta que está llamando [self count](un captador de propiedades) dos veces en cada iteración a través del bucle. Creo que sacarlo del circuito vale la pena perder la concisión.
Kristopher Johnson
1
Y es por eso que todavía prefiero en [object method]lugar de object.method: la gente tiende a olvidar que lo último no es tan barato como acceder a un miembro de estructura, viene con el costo de una llamada al método ... muy malo en un bucle.
DarkDust
Gracias por las correcciones. Asumí erróneamente que el conteo estaba en caché, por alguna razón. Se actualizó la respuesta.
gregoltsov
10

Si importa GameplayKit, hay una shuffledAPI:

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

let shuffledArray = array.shuffled()
andreacipriani
fuente
Tengo myArray y quiero crear un nuevo shuffleArray. ¿Cómo lo hago con Objective - C?
Omkar Jadhav
shuffledArray = [array shuffledArray];
andreacipriani
Tenga en cuenta que este método es parte, por GameplayKitlo que debe importarlo.
AnthoPak
9

Una solución ligeramente mejorada y concisa (en comparación con las respuestas principales).

El algoritmo es el mismo y se describe en la literatura como " Shuffle Fisher-Yates ".

En el objetivo-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

En Swift 3.2 y 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))))
        }
    }
}

En Swift 3.0 y 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])
        }
    }
}

Nota: Una solución más concisa en Swift es posible desde iOS10 usando GameplayKit.

Nota: También está disponible un algoritmo para barajar inestable (con todas las posiciones obligadas a cambiar si cuenta> 1)

Coeur
fuente
¿Cuál sería la diferencia entre esto y el algoritmo de Kristopher Johnson?
Iulian Onofrei
@IulianOnofrei, originalmente, el código de Kristopher Johnson no era óptimo y mejoré su respuesta, luego fue editado nuevamente con alguna verificación inicial inútil agregada. Prefiero mi forma concisa de escribirlo. El algoritmo es el mismo y se describe en la literatura como " Shuffle Fisher-Yates ".
Cœur
6

Esta es la forma más simple y rápida de barajar NSArrays o NSMutableArrays (el rompecabezas de objetos es un NSMutableArray, contiene objetos de rompecabezas. He agregado al índice variable de objetos de rompecabezas que indica la posición inicial en la matriz)

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

salida de registro:

 #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

también puede comparar obj1 con obj2 y decidir qué desea devolver posibles valores son:

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

fuente
1
También para esta solución, use arc4random () o seed.
Johan Kool
17
Este shuffle es defectuoso, como se ha recordado recientemente a Microsoft: robweir.com/blog/2010/02/microsoft-random-browser-ballot.html .
Raphael Schweikert
De acuerdo, defectuoso porque "la clasificación requiere una definición de orden coherente" como se señala en ese artículo sobre la EM. Parece elegante, pero no lo es.
Jeff
2

Hay una buena biblioteca popular, que tiene este método como parte, llamada SSToolKit en GitHub . El archivo NSMutableArray + SSToolkitAdditions.h contiene un método aleatorio. Puedes usarlo también. Entre esto, parece haber toneladas de cosas útiles.

La página principal de esta biblioteca está aquí .

Si usa esto, su código será así:

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

Esta biblioteca también tiene un Pod (ver CocoaPods)

Denis Kutlubaev
fuente
2

Desde iOS 10, puedes usar NSArray shuffled()de GameplayKit . Aquí hay un ayudante para Array en 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())
    }
}
Coeur
fuente
1

Si los elementos tienen repeticiones.

por ejemplo, matriz: AAABB o BBAAA

La única solución es: ABABA

sequenceSelected es un NSMutableArray que almacena elementos de la clase obj, que son punteros a alguna secuencia.

- (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;
                }
            }
        }
    }
}
Punto gamma
fuente
usar a staticevita trabajar en varias instancias: sería mucho más seguro y legible usar dos métodos, uno principal que baraja y llama al método secundario, mientras que el método secundario solo se llama a sí mismo y nunca se reorganiza. También hay un error de ortografía.
Cœur
-1
NSUInteger randomIndex = arc4random() % [theArray count];
kal
fuente
2
o arc4random_uniform([theArray count])sería aún mejor, si está disponible en la versión de Mac OS X o iOS que está apoyando.
Kristopher Johnson
1
Me dieron así el número se repetirá.
Vineesh TP
-1

La respuesta de Kristopher Johnson es bastante buena, pero no es totalmente al azar.

Dada una matriz de 2 elementos, esta función devuelve siempre la matriz inversa, porque está generando el rango de su azar sobre el resto de los índices. Una shuffle()función más precisa sería como

- (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
fuente
Creo que el algoritmo que ha sugerido es un "shuffle ingenuo". Ver blog.codinghorror.com/the-danger-of-naivete . Creo que mi respuesta tiene un 50% de posibilidades de intercambiar los elementos si solo hay dos: cuando i es cero, arc4random_uniform (2) devolverá 0 o 1, por lo que el elemento cero se intercambiará consigo mismo o se intercambió con el primero elemento. En la siguiente iteración, cuando i es 1, arc4random (1) siempre devolverá 0, y el elemento i-ésimo siempre se intercambiará consigo mismo, lo cual es ineficiente pero no incorrecto. (Tal vez la condición del bucle debería ser i < (count-1)).
Kristopher Johnson
-2

Editar: esto no es correcto. Para fines de referencia, no eliminé esta publicación. Ver comentarios sobre la razón por la cual este enfoque no es correcto.

Código simple aquí:

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