Блог

Каков наилучший метод генерации всех возможных NSArrays, учитывая, что в NSArray есть только 2 возможных записи (X или Y). Некоторые значения в массиве уже будут назначены перед запуском и не могут быть изменены.

Например, в приведенном здесь массиве 16 возможных перестановок дают, что позиции 1 и 2 уже привязаны к X amp; Y соответственно и не могут быть изменены. Позиция 0 может принимать X или Y, но не может быть пустой. Например, мудрые позиции 3,4,5.


0:[ ]
1:[X]
2:[Y]
3:[ ]
4:[ ]
5:[ ]


[ ] просто обозначает, что этой позиции в массиве ничего не назначено, поэтому при вычислении всех перестановок необходимо назначить либо X, либо Y. Это одномерный массив или размер 6. Я пишу на Objective-C для устройства iOS. Любые рекомендации здесь будут оценены.

Спасибо — C

Я думаю, я понимаю, к чему вы стремитесь: сгенерируйте перестановки из 6 объектов, выбранных из набора длины 2 (@»X» и @»Y»), исключая объекты с заданным шаблоном.

Здесь есть хороший компромисс между скоростью и пространством, потому что существует только 64 перестановки из 6 объектов, выбранных из набора длины 2. Полный набор достаточно мал, чтобы его можно было вычислить заранее и держать под рукой. При этом алгоритм оказывается простым фильтром по шаблону «фиксированных» позиций.

Нам нужен способ представления этого шаблона. NSArrays не являются позиционными, как массивы C. Массив с числом 6 должен содержать объект с каждым индексом 1 ..5, поэтому простой подход заключается в выборе другого объекта для представления «нефиксированных» позиций (операционный эквивалент «[ ]»).). Например, если мы используем @"*" , ( NSNull экземпляры тоже являются достойным выбором), шаблон, исключенный из операции, будет выглядеть следующим образом:

  @[ @"*", @"X", @"Y", @"*", @"*", @"*" ]
  

Итак, давайте начнем с полного набора перестановок. Вычислите их лениво (вычислите и кэшируйте при первом вызове, затем верните кэшированный результат после этого):

 @property(strong,nonatomic) NSArray *permutations;

- (NSArray *)permutations {
    if (!_permutations) {
        NSSet *set = [NSSet setWithArray:@[ @"X", @"Y"]];
        _permutations = [self permute:set count:6];
    }
    return _permutations;
}

// simple recursive algorithm to permute
- (NSArray *)permute:(NSSet *)set count:(NSInteger)count {
    NSMutableArray *result = [@[] mutableCopy];
    if (count == 1) {
        for (id object in [set allObjects]) [result addObject:@[object]];
        return resu<
    } else {
        NSArray *smaller = [self permute:set count:count-1];
        for (id object in [set allObjects]) {
            for (NSArray *array in smaller) {
                NSMutableArray *m = [array mutableCopy];
                [m insertObject:object atIndex:0];
                [result addObject:m];
            }
        }
        return  resu<
    }
}
  

Это приведет к таким перестановкам, как…

 @[ @[ @"X", @"X", @"X", @"X", @"X", @"X" ],
   @[ @"X", @"X", @"X", @"X", @"X", @"Y" ], // ... and so on
  

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

При этом проблема сводится к фильтру. Вот проверка того, соответствует ли данный массив шаблону (используя @»*» в качестве подстановочного знака):

 - (BOOL)array:(NSArray *)array matchesPattern:(NSArray *)pattern {
    for (NSInteger i=0; i<array.count; i  ) {
        if (![pattern[i] isEqualToString:@"*"] amp;amp; ![array[i] isEqualToString:pattern[i]]) return NO;
    }
    return YES;
}
  

Примените этот фильтр в качестве предиката:

 NSArray *pattern =@[ @"*", @"X", @"Y", @"*", @"*", @"*" ];
NSPredicate *predicate = [NSPredicate predicateWithBlock:^BOOL(id evaluatedObject, NSDictionary * bindings) {
    NSArray *a = (NSArray *)evaluatedObject;
    return [self array:a matchesPattern:pattern];
}];
  

И выполните фильтрацию:

 NSArray *permutations = [self permutations];
NSArray *result = [permutations filteredArrayUsingPredicate:predicate];
  

Я протестировал это с параметрами OP и несколькими вариантами.