1

Possible Duplicate:
Generating permutations of NSArray elements

Let's say that I have

[1,2]

And I want to get

{1}
{2}
{1, 2}
{2, 3}
Community
  • 1
  • 1
Alejandro Cotilla
  • 2,501
  • 1
  • 20
  • 35
  • 6
    Where does `{2, 3}` come from? – irrelephant Nov 30 '12 at 01:26
  • Look up "permutations and combinations" on the web or in a math book. – Hot Licks Nov 30 '12 at 01:27
  • @NSPostWhenIdle et. al. - The question appears to be about power set (all possible subsets) not permutations (all possible orderings) as is the case in the supposed duplicate. These are different concepts. – danh Nov 30 '12 at 05:38

1 Answers1

8

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

danh
  • 62,181
  • 10
  • 95
  • 136