All possible combinations without repetition from an NSArray

Question

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 ifs.

Answer 1

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 2^num_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.