WebOrCode WebOrCode - 4 months ago 21
Objective-C Question

All possible combinations without repetition from an NSArray

Let say that I have an array with 3 numbers:

NSArray *array = @[@1, @2, @3];


And I want to make all combinations without repetition.

So what I need is this:

( 1 )

( 2 )

( 3 )

( 1, 2 )

( 2, 3 )

( 1, 3 )

( 1, 2, 3 )

The current code that I have is this:

NSArray *array = @[@1, @2, @3];
int numberOfCardsOTable = [array count];

//NSLog(@"array = %@", array);

for (int lenghtOfArray = 1; lenghtOfArray <= numberOfCardsOTable; lenghtOfArray++)
{
for (int i = 0; i < numberOfCardsOTable; i++)
{
// array bound check
if (i + lenghtOfArray > numberOfCardsOTable) {
continue;
}

NSArray *subArray = [[NSMutableArray alloc] init];

subArray = [array subarrayWithRange:NSMakeRange(i, lenghtOfArray)];

NSLog(@"array = %@", subArray);
}
}


But this code is missing ( 1, 3 ).

I will need to do this for a source array up to 8 numbers long.

With 8 numbers there are 255 combinations, and my algorithm will miss a lot, so that will be lots of
if
s.

Answer

Since you seem to want your combinations to be in the same order as the original set, what you're doing is the same as counting to 2num_choices and selecting the objects corresponding to the set bits. You can make this really easy with a little help from a category method I've written for NSIndexSet.

@implementation NSIndexSet (WSSNoncontiguous)

+ (instancetype)WSSIndexSetFromMask:(uint64_t)mask
{
    NSMutableIndexSet * set = [NSMutableIndexSet indexSet];

    for( uint64_t i = 0; i < 64; i++ ){
        if( mask & (1ull << i) ){
            [set addIndex:i];
        }
    }

    return set;
}

@end

This creates an NSIndexSet whose contents are the indexes of the bits that are set in the mask. You can then use that index set with -[NSArray objectsAtIndexes:] to grab your combinations:

NSArray * choices = @[...];
uint64_t num_combos = 1ull << [choices count];    // 2**count
NSMutableArray * combos = [NSMutableArray new];
for( uint64_t i = 1; i < num_combos; i++ ){
    NSIndexSet * indexes = [NSIndexSet WSSIndexSetFromMask:i];
    [combos addObject:[choices objectsAtIndexes:indexes]];
}

Obviously this only works for a choices that has sixty-four or fewer members, but that would end up being a very large number of combos anyways.

Comments