所有可能的组合，无需重复NSArray [英] All possible combinations without repetition from an NSArray

问题描述

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

Let say that I have an array with 3 numbers:

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

我想使所有组合都没有重复.
所以我需要的是:
(1)
(2)
(3)
(1，2)
(2，3)
(1，3)
(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);
    }
}

但是缺少此代码(1、3).

But this code is missing ( 1, 3 ).

对于长度最多为8个数字的源数组，我将需要执行此操作.
如果有8个数字，则有255个组合，而我的算法会遗漏很多，因此会有很多if s.

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 ifs.

推荐答案

由于您似乎希望组合与原始组合的顺序相同，因此您所做的等同于计算2 ^num_choices 并选择与设置的位相对应的对象.在我为NSIndexSet编写的类别方法的一点帮助下，您可以使此操作真正简单.

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

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

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

很明显，这仅适用于成员数量少于或等于64的choices，但无论如何最终还是很多连击.

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.

这篇关于所有可能的组合，无需重复NSArray的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！