The pragmatic answer typically involves digging in some favourite tome. Something like Numerical Recipes, or The Algorithm Design Manual. All very handy. And perfect if the implementations match your language and environment requirements. Otherwise you’re left to wade through the theory, or try to port. To understand or to port? That is the question. If, like me, you find yourself choosing between time pressures and interest, you normally end up porting.

It’s always handy if someone else has already been through the pain and made the gain for you. Quickly digging around the Internet (roughly translated means Googling) might find what you want. But not always exactly. Cutting a long story short, this article tries to fill the gap between permutations and Objective-C.

Already done

Ah, but work already done? Check out Marko Riedel’s GNUstep cookbook. Marko publishes some Objective-C code for a permutation enumerator. See section Counting II: Permutation enumerator.

I have a problem with it though. It’s sloppy. Call me a fusspot but I like quality code. Marco’s work while may be functional bears the hallmarks of cobbling: a done flag, zone-allocated array of ints, no testing for allocation failure. Do I ask too much? Maybe.

So not already out there! Until now.

Ruby Tuesday

I’m a fan of Ruby (and Rails). Ruby equips a useful permutation enumerator class written by Florian Frank. It has a number of admirable qualities, including simplicity. I like classes with low amounts of internal state. They have fewer bugs in general—maintenance and comprehension easier. True, it has some more advanced features that most would not require. Still, these can be added later when needs arise.

Only one strange thing about Florien’s implementation: the @last instance variable gets assigned by the initialiser but then ignored. Apart from its getter method, other instance methods re-compute last by asking for the size factorial. Strange. Never mind, our implementation will fix that oddity.

So here’s the mission: develop an Objective-C permutation enumerator class based on Florian’s Ruby implementation, which is itself based on algorithms presented in Steve Skiena’s The Algorithm Design Manual! Imitation is the sincerest form of flattery. It gives the outcome a satisfactory pedigree. It’s also more ideal than most porting source-target pairs since their are many conceptual similarities between Objective-C and Ruby, i.e. grounded in C, aspiring to Smalltalk.

Another advantage of this approach is that getting to mental grips with the underlying algorithm becomes unnecessary. Lazy bones!

Test-driven approach

As is good practise, let’s start with a test. It’s the agile way. It will mark the development iterations beginning and end: begin with the test fails, end when it succeeds.

Let’s take a very simple test: permuting an array of 3 elements. Our test wants to know how many alternative permutations exist. For arguments sake, the three elements are letters a, b and c. If we had an enumerator called say RRPermutation that conforms to the NSEnumerator protocol, our test would output the permutations using the code below.

#import <Foundation/Foundation.h>

#import <RRFoundation/RRPermutation.h>

int main(int argc, char *argv[])
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    RRPermutation *perm = [[RRPermutation alloc] initWithSize:3];
    for (id indices in perm)
    {
        // Project the indices into the test string "abc". Objective-C does not
        // have a "project" method, as such. We'll need to do this part by hand.
        NSString *s = @"";
        for (id i in indices)
        {
            s = [s stringByAppendingString:[@"abc" substringWithRange:NSMakeRange([i unsignedIntegerValue], 1)]];
        }
        NSLog(@"%@", s);
    }
    [perm release];
    [pool drain];
    return 0;
}

Note! The test code takes permutation values as indices not values.

This is important. It means that permutation enumeration is value-type indifferent. The design and implementation does not want to focus on one particular type of value, e.g. string or number. Rather, enumeration of permutation should be generic.

Hence, the enumeration outputs indices. You then apply (or project, in Ruby terms) the indices to whatever values you want. That’s neutral. That’s good. Otherwise, we’re looking at duplicate implementations for different types, since Objective-C types do not all have first-class status albeit they may have object wrappers. This approach however answers all requirements, including projecting into non-object sequences such as C arrays or plain C strings.

Test tool in hand. What next?

Interface

The preceding test case employs just two interface methods,

• the initialiser, initWithSize: and
• the iteration method, nextObject.

Of course, these aren’t the only methods necessary. They are only the permuting public interface. Add a designated initialiser, a set of accessors and some internals. Add a splash of instance variables (size and rank). This is what you get: listing of RRPermutation.h below.

#import <Foundation/Foundation.h>

@interface RRPermutation : NSEnumerator
{
    NSUInteger size, rank;
}

- (id)initWithSize:(NSUInteger)aSize rank:(NSUInteger)aRank;
- (id)initWithSize:(NSUInteger)aSize;

- (NSUInteger)size;
- (NSUInteger)rank;
- (NSUInteger)last;

- (void)setRank:(NSUInteger)newRank;
    // Rank ranges from 0 to factorial of size, less one, i.e. last. Use
    // setRank:0 to reset a permutation enumerator.

- (id)nextObject;
    // Send nextObject repeatedly to get the next array of permutation
    // indices. Answers nil after the last. Note that you cannot reset the
    // enumeration using the enumerator interface, although permutation
    // internals allow it.

// Following methods are generally for internal use and might be considered
// private. Nevertheless, feel free to access them for testing and debugging or
// other purposes if you wish. They are query methods, operations without side
// effects on enumerator state. So no pitfalls to avoid.

- (NSArray *)unrankIndices:(NSUInteger)m;

@end

Implementation #1

Listing of RRPermutation.m as follows.

#import "RRPermutation.h"

#import "RRFactorial.h"

@implementation RRPermutation

// designated initialiser
- (id)initWithSize:(NSUInteger)aSize rank:(NSUInteger)aRank
{
    if ((self = [super init]))
    {
        size = aSize;
        rank = aRank;
        // Rank steps by one, starting at zero, ending at RRFactorial(size) - 1;
        // no need to store this value because RRFactorial does all the storing
        // for us in its secret cache.
    }
    return self;
}

- (id)initWithSize:(NSUInteger)aSize
{
    return [self initWithSize:aSize rank:0];
}

#pragma mark Accessors

- (NSUInteger)size
{
    return size;
}

- (NSUInteger)rank
{
    return rank;
}

- (NSUInteger)last
{
    return RRFactorial(size) - 1;
}

- (void)setRank:(NSUInteger)newRank
{
    rank = newRank;
}

#pragma mark Enumerator

- (id)nextObject
{
    return rank < RRFactorial(size) ? [self unrankIndices:rank++] : nil;
}

- (NSArray *)unrankIndices:(NSUInteger)m
{
    NSMutableArray *result = [NSMutableArray arrayWithCapacity:size];
    NSUInteger i;
    for (i = 0; i < size; i++)
    {
        [result addObject:[NSNumber numberWithUnsignedInteger:0]];
    }
    for (i = 0; i < size; i++)
    {
        NSUInteger f = RRFactorial(i);
        NSUInteger x = m % (f * (i + 1));
        m -= x;
        x /= f;
        [result replaceObjectAtIndex:size - i - 1 withObject:[NSNumber numberWithUnsignedInteger:x]];
        // At this point, Florian decrements x in preparation for the following
        // comparisons with values from the result array. This assumes that x
        // can be negative however. In our case, it cannot because we implement
        // indices using NSUInteger (unsigned) as is the Foundation framework's
        // wont for array indices. To abviate the decrement, the subsequent test
        // becomes greater-than-or-equal-to instead of greater-than. Problem
        // solved, and simplifies the code too.
        // x -= 1;
        NSUInteger j;
        for (j = size - i; j < size; j++)
        {
            NSUInteger y = [[result objectAtIndex:j] unsignedIntegerValue];
            if (y >= x)
            {
                [result replaceObjectAtIndex:j withObject:[NSNumber numberWithUnsignedInteger:y + 1]];
            }
        }
    }
    return result;
}

@end

The size attribute describes the size of the permutation required: 3 for permutations of three elements, 7 for seven, etc. During enumeration, the rank attribute ranges in the integer interval [0, size! - 1] where size! refers to the factorial of size.

Testing

Applying the testing tool produces:

abc
acb
bac
bca
cab
cba

Exactly right!

Projecting indices

Taking a look again at the test code, the loop for projecting the resulting permutation indices needs simplifying. Does it not? It’s likely something that will be needed time and again, especially when using permutations. It’s a loop. Each iteration takes the next index (an NSNumber) and looks up an object from an array of values. The indexed elements combine to form a new array. Project indices! It needs a new NSArray method, like this:

- (NSArray *)projectIndices:(NSArray *)indices
{
    NSMutableArray *result = [NSMutableArray arrayWithCapacity:[indices count]];
    for (NSNumber *i in indices)
    {
        [result addObject:[self objectAtIndex:[i unsignedIntegerValue]]];
    }
    return result;
}

Using this, adding it to an Objective-C category applied to NSArray, lets the test case simplify to:

        NSLog(@"%@", [[abc projectIndices:indices] componentsJoinedByString:@","]);

This replaces the test’s inner loop. Variable abc is an NSArray pointer equal to the array given by [NSArray arrayWithObjects:@"a", @"b", @"c", nil].

Niggles

Call me fussy again, but there is a notable weakness. The implementation of unrankIndices uses a mutable array of NSNumber objects. Yet, the implementation really only requires a small fixed array of NSUIntegers. It might be more efficient to generate the array of unsigned integers first using a stack-allocated buffer, using alloca. Then, before returning the result, convert the raw C array of integers to an NSArray of NSNumber objects.

It’s a small difference. But is it worthwhile?

Download sources

MIT-licensed sources here.