канонический способ рандомизировать NSArray в Objective C

Question

Есть ли канонический способ рандомизировать массив в Objective C?

Answer 1

Моя служебная библиотека определяет эту категорию в NSMutableArray, чтобы сделать это:

@interface NSMutableArray (ArchUtils_Shuffle)
- (void)shuffle;
@end

// Chooses a random integer below n without bias.
// Computes m, a power of two slightly above n, and takes random() modulo m,
// then throws away the random number if it's between n and m.
// (More naive techniques, like taking random() modulo n, introduce a bias 
// towards smaller numbers in the range.)
static NSUInteger random_below(NSUInteger n) {
    NSUInteger m = 1;

    // Compute smallest power of two greater than n.
    // There's probably a faster solution than this loop, but bit-twiddling
    // isn't my specialty.
    do {
        m <<= 1;
    } while(m < n);

    NSUInteger ret;

    do {
        ret = random() % m;
    } while(ret >= n);

    return ret;
}

@implementation NSMutableArray (ArchUtils_Shuffle)

- (void)shuffle {
    // http://en.wikipedia.org/wiki/Knuth_shuffle

    for(NSUInteger i = [self count]; i > 1; i--) {
        NSUInteger j = random_below(i);
        [self exchangeObjectAtIndex:i-1 withObjectAtIndex:j];
    }
}

@end

Убедитесь, что вы запустили генератор случайных чисел (например, srandom(time(NULL))) перед вызовом; в противном случае вывод не будет очень случайным.

Answer 2

Вот оно!

- (NSArray*)shuffleArray:(NSArray*)array {

    NSMutableArray *temp = [[NSMutableArray alloc] initWithArray:array];

    for(NSUInteger i = [array count]; i > 1; i--) {
        NSUInteger j = arc4random_uniform(i);
        [temp exchangeObjectAtIndex:i-1 withObjectAtIndex:j];
    }

    return [NSArray arrayWithArray:temp];
}

Answer 3

if ([array count] > 1) {
    for (NSUInteger shuffleIndex = [array count] - 1; shuffleIndex > 0; shuffleIndex--)
        [array exchangeObjectAtIndex:shuffleIndex withObjectAtIndex:random() % (shuffleIndex + 1)];
}

Обязательно заполняйте функцию random () с помощью srandomdev () или srandom ().

Answer 4

Нет встроенного в SDK, если вы об этом спрашиваете.

Вы можете использовать любой алгоритм рандомизации или тасования, какой пожелаете. Различные алгоритмы имеют разные компромиссы с точки зрения случайности, эффективности и т. Д.

http://en.wikipedia.org/wiki/Shuffling#Shuffling_algorithms

Для алгоритмов, которые перемешивают «на месте», начинают с изменяемого массива, используйте

insertObject:atIndex:
removeObjectAtIndex:

Для алгоритмов, которые восстанавливают массив, передайте его оригиналу и создайте новый массив.

Answer 5

Мое решение - это метод категории, который возвращает копию массива (автоматически выпущенную) с рандомизированными элементами (с использованием arc4random).

@interface NSArray (CMRandomised)

/* Returns a copy of the array with elements re-ordered randomly */
- (NSArray *)randomised;

@end

/* Returns a random integer number between low and high inclusive */
static inline int randomInt(int low, int high)
{
    return (arc4random() % (high-low+1)) + low;
}

@implementation NSArray (CMRandomised)

- (NSArray *)randomised
{
    NSMutableArray *randomised = [NSMutableArray arrayWithCapacity:[self count]];

    for (id object in self) {
        NSUInteger index = randomInt(0, [randomised count]);
        [randomised insertObject:object atIndex:index];
    }
    return randomised;
}

@end

Answer 6

NSArray рандомизация как метод категории Objective C:

@implementation NSArray (NGDataDynamics)

- (NSArray *)jumbled
{
  NSMutableArray *jumbled = self.mutableCopy;

  NSUInteger idx = self.count-1;
  while(idx)
  {
    [jumbled exchangeObjectAtIndex:idx
                 withObjectAtIndex:arc4random_uniform(idx)];
    idx--;
  }

  return jumbled;
}

@end

Как видно: NSArray Randomization & Psychedelia

Answer 7

Не существует канонического способа без создания категории на NSArray (т.е. есть метод экземпляра, например arrayWithRandomizedIndices) или NSMutableArray (т.е. есть метод, подобный randomizeIndices).

Вот пример из моей библиотеки, часть категории на NSMutableArray. Он будет случайным образом переупорядочивать массив, а не перемешивать несколько записей.

- (void) randomizeIndices
{
  if (self == nil || [self count] <= 1)
  {
    return;
  }

  int count = [self count];

  NSMutableArray* copySelf = [NSMutableArray arrayWithArray:self];
  NSMutableArray* mutableResultArray = [NSMutableArray alloc];
  mutableResultArray = [mutableResultArray initWithCapacity:count];
  [mutableResultArray autorelease];

  int objectsMovedCount = 0;

  for (int i = 0; i < count; i++)
  {
    int index = rand() % (count - objectsMovedCount);
    id anObject = [copySelf objectAtIndex:index];
    [mutableResultArray addObject:anObject];
    [copySelf removeObjectAtIndex:index];
    objectsMovedCount++;
  }
  [self setArray:mutableResultArray];
}

Вызовите srand(time(0)); или что-то подобное перед вызовом этого метода или в начале метода.