所有可能的组合,无需重复NSArray

Question

假设我有一个包含3个数字的数组:

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

而且我想在不重复的情况下完成所有组合.
所以我需要的是:
(1)
(2)
(3)
(1,2)
(2,3)
(1,3)
(1,2,3)

我当前的代码是这样的:

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);
    }
}

但是这段代码丢失了(1,3).

我需要为最多8个数字的源数组执行此操作.
有8个数字,有255个组合,我的算法会遗漏很多,所以这将是很多ifs.

Answer 1

由于您似乎希望组合与原始组的顺序相同,因此您所做的与计数到2 ^num_choices并选择与设置位对应的对象相同.您可以通过我编写的类别方法获得一些帮助,使这个变得非常简单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

这将创建一个NSIndexSet内容是掩码中设置的位的索引.然后,您可以使用该索引集-[NSArray objectsAtIndexes:]来获取组合:

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]];
}

显然,这仅适用于choices拥有64个或更少成员的人,但无论如何最终会成为非常多的组合.