WebOrCode - 1 year ago 62

Objective-C 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

`if`

Answer Source

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.