Generating permutations of NSArray elements

Question

Let's say I have an NSArray of NSNumbers like this: 1, 2, 3

Then the set of all possible permutations would look something like this:

1, 2, 3

1, 3, 2

2, 1, 3

2, 3, 1

3, 1, 2

3, 2, 1

What's a good way to do this in XCode?

Answer 1

YEAH!

NSNumber *n1 = [NSNumber numberWithInteger:1];
NSNumber *n2 = [NSNumber numberWithInteger:2];
NSNumber *n3 = [NSNumber numberWithInteger:3];
NSArray *array = [NSArray arrayWithObjects:
    [NSArray arrayWithObjects:n1,n2,n3,nil],
    [NSArray arrayWithObjects:n1,n3,n2,nil],
    [NSArray arrayWithObjects:n2,n1,n3,nil],
    [NSArray arrayWithObjects:n2,n3,n1,nil],
    [NSArray arrayWithObjects:n3,n1,n2,nil],
    [NSArray arrayWithObjects:n3,n2,n1,nil],nil];

Answer 2

There might be a better way to do this (in-place, or something), but this seems to work:

Header:

@interface NSArray (PermutationAdditions)

- (NSArray *)allPermutations;

@end

Implemetation:

@implementation NSArray (PermutationAdditions)

NSInteger *pc_next_permutation(NSInteger *p, const NSInteger size) {
    // slide down the array looking for where we're smaller than the next guy
    NSInteger i;
    for (i = size - 1; p[i] >= p[i + 1]; --i) { }

    // if this doesn't occur, we've finished our permutations
    // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
    if (i == -1)
        return NULL;

    NSInteger j;
    // slide down the array looking for a bigger number than what we found before
    for (j = size; p[j] <= p[i]; --j) { }

    // swap them
    NSInteger tmp = p[i]; p[i] = p[j]; p[j] = tmp;

    // now reverse the elements in between by swapping the ends
    for (++i, j = size; i < j; ++i, --j) {
        tmp = p[i]; p[i] = p[j]; p[j] = tmp;
    }

    return p;
}

- (NSArray *)allPermutations {
    NSInteger size = [self count];
    NSInteger *perm = malloc(size * sizeof(NSInteger));

    for (NSInteger idx = 0; idx < size; ++idx)
        perm[idx] = idx;

    NSInteger j = 0;

    --size;

    NSMutableArray *perms = [NSMutableArray array];

    do {
        NSMutableArray *newPerm = [NSMutableArray array];

        for (NSInteger i = 0; i <= size; ++i)
            [newPerm addObject:[self objectAtIndex:perm[i]]];

        [perms addObject:newPerm];
    } while ((perm = pc_next_permutation(perm, size)) && ++j);

    return perms;
}

@end

To use it, simply #import the header file, and call [yourArray allPermutations]; the method will return an array containing arrays for each permutation.

[Code adapted from PHP code here.]