objective-c – 所有可能的组合,无需重复NSArray

发布时间：2020-12-16 09:52:59 所属栏目：百科来源：网络整理

导读：假设我有一个包含3个数字的数组： NSArray *array = @[@1,@2,@3]; 而且我想在不重复的情况下完成所有组合. 所以我需要的是： (1) (2) (3) (1,2) (2,3) (1,2,3) 我当前的代码是这样的： NSArray *array = @[@1,@3];int numberOfCardsOTable = [array count];/

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

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

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

我当前的代码是这样的：

NSArray *array = @[@1,@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.

解决方法

由于您似乎希望组合与原始组的顺序相同,因此您所做的与计算2num_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个或更少成员的选择,但最终会成为非常多的组合.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!