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.

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)

{
NSMutableIndexSet * set = [NSMutableIndexSet indexSet];

for( uint64_t i = 0; i < 64; i++ ){
if( mask & (1ull << 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];
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.