objective-c - 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 种组合，我的算法会漏掉很多，所以会有很多 if。

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

显然，这仅适用于具有 64 个或更少成员的 choices，但无论如何，这最终将是非常大量的组合。