iphone - 如何从Objective-C中的数组中获取所有可能的数字组合

Question

可能重复：
生成 NSArray 元素的排列

假设我有

[1,2]

我想得到

{1}
{2}
{1, 2}
{2, 3}

Answer 1

I think the name of the thing you're looking for is 'power set'. It sounded fun, so here's a crack at it. I relied on this very concise article for the algorithm. I'm not sure if this is efficient (...actually, I'm sure this is inefficient) over large sets.

// answer the powerset of array: an array of all possible subarrays of the passed array
- (NSArray *)powerSet:(NSArray *)array {

    NSInteger length = array.count;
    if (length == 0) return [NSArray arrayWithObject:[NSArray array]];

    // get an object from the array and the array without that object
    id lastObject = [array lastObject];
    NSArray *arrayLessOne = [array subarrayWithRange:NSMakeRange(0,length-1)];

    // compute the powerset of the array without that object
    // recursion makes me happy
    NSArray *powerSetLessOne = [self powerSet:arrayLessOne];

    // powerset is the union of the powerSetLessOne and powerSetLessOne where
    // each element is unioned with the removed element
    NSMutableArray *powerset = [NSMutableArray arrayWithArray:powerSetLessOne];

    // add the removed object to every element of the recursive power set
    for (NSArray *lessOneElement in powerSetLessOne) {
        [powerset addObject:[lessOneElement arrayByAddingObject:lastObject]];
    }
    return [NSArray arrayWithArray:powerset];
}

If you think this is a keeper, you could make it a category method on array and drop the parameter. Test it like this...

NSLog(@"empty = %@", [self powerSet:[NSArray array]]);
NSLog(@"one item = %@", [self powerSet:[NSArray arrayWithObject:@"a"]]);
NSLog(@"two items = %@", [self powerSet:[NSArray arrayWithObjects:@"a", @"b", nil]]);
NSLog(@"three items = %@", [self powerSet:[NSArray arrayWithObjects:@"a", @"b", @"c", nil]]);

I did only these tests, and the output looked good. Spoiler alert: the three item test looks roughly like this on my console (with \n's removed):

three items = ((), (a), (b), (a,b), (c), (a,c), (b,c), (a,b,c))