Permutations! I’ve hit this issue quite a number of times in my life: at university, at work. It’s not unusual to encounter problems where it’s very handy to able to iterate all possible permutations of something. And catch is: standard libraries sometimes do not offer any help. The engineer is left to tackle the problem by him- or herself.
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.
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.
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!
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
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?
The preceding test case employs just two interface methods,
* the initialiser,
* the iteration method,
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 (
rank). This is what you get: listing of
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
RRPermutation.m as follows.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
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.
Applying the testing tool produces:
abc acb bac bca cab cba
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:
1 2 3 4 5 6 7 8 9
Using this, adding it to an Objective-C category applied to
NSArray, lets the test case simplify to:
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].
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
It’s a small difference. But is it worthwhile?
MIT-licensed sources here.