Code Code - 10 months ago 53
Objective-C Question

Generating all possible permutations/combinations of a semi populated array

What is the best method of generating all the possible NSArrays given that there are only 2 possible entries(X or Y) in the NSArray. Some of the values in the array will already be assigned before you start and cannot be changed.

For example the array here has 16 possible permutations give that position 1 and 2 are already locked to X & Y respectively and can not be changed. Position 0 can take an X or a Y, but can't be empty. Like wise positions 3,4,5.

0:[ ]
3:[ ]
4:[ ]
5:[ ]

The [ ] just denotes nothing assigned to that position in the array so will need to be assigned either an X or Y when calculating all the permutations. Its a single dimension array or size 6.
I'm coding in Objective-C for an iOS device. Any guidance here would be appreciated.

Thanks - C

Answer Source

I think I understand what you're going for: generate permutations of 6 objects chosen from a set of length 2 (@"X" and @"Y") excluding those with a given pattern.

There's a good speed/space trade-off here, because there are only 64 permutations of 6 objects chosen from a set of length 2. The complete set is small enough to be computed early and be kept on hand. With that, the algorithm turns out to be a simple filter over the pattern of "fixed" positions.

We need a way to represent that pattern. NSArrays aren't positional like C arrays. An array of count 6 must contain an object at every index 1..5, so a simple approach is to choose another object to represent "un-fixed" positions, (the OP equivalent of "[ ]"). For example, if we use @"*", (NSNull instances are a decent choice, too), the OP excluded pattern would look like this literal:

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

So lets start with the complete set of permutations. Compute these lazily (compute and cache on the first call, then return a cached result thereafter):

@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 result;
    } 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  result;

This will produce permutations like...

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

You could even do this at compile time, and include that result as a 64 element array literal in your app.

With that, the problem is reduced to a filter. Here's a test for whether a given array matches a pattern (using @"*" as a wild card):

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

Apply that filter as a predicate:

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

And do the filtering:

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

I tested this with OP params and a few variations.