1.2 Counting II: Permutation enumerator

by Marko Riedel

1.2.1 Idea

Suppose you wish to permute n items that are stored in an array. You select the last item, then the next-to-last etc. (You could also start from the beginning, going first, second, third etc.) You have n choices for the last item. Then you have n- 1 choices for the next-to-last item etc. Every permutation corresponds to a vector of choices. If we can enumerate these vectors, then we can enumerate permutations.

A sequence of integers up to some limit is easily enumerated by starting at zero and adding one until we get to the limit. Observe the process in binary: 0,1,10,11,100,101,110,111 etc. The weights of the digits are 1,2,4,8 etc., starting from the right. Now consider a base where the weights are 1,2,6,24,120. This is the so-called factorial base (a Cantor base). Individual digits range from 0 to w2∕w1 - 1, where w1 is the weight at that position and w2 the weight at the next position. By the same counting process as in binary, we get 0,1,10,11,20,21,100,101 etc. Addition in this base is the same as regular addition. To add one, start at the right and increment going to the left until you get a digit that is not the maximum for that position where maximal digits are replaced by zero. E.g. the last digit of 11 is maximal in its position while the second is not, so (1)(1) + 1 yields (2)(0).

We can enumerate permutations by counting from 0 to n! - 1 in the factorial base. The first digit indicates how to choose the last element, the second the next-to-last element and so on.

1.2.2 Implementation

We will implement an enumerator for permutations and add a category to NSArray.

 
@interface PermutationEnumerator : NSEnumerator 
{ 
    NSArray *array; 
    int *swapLocs; 
    int count; 
    BOOL done; 
} 
 
- (id)initWithArray:(NSArray *)anArray; 
- (id)nextObject; 
- (void)dealloc; 
 
@end

The state of the enumerator is defined by the array whose elements are being permuted, the number of elements in the array, the counter whose factorial base digits we store in the array  swapLocs and a flag that indicates whether we are done.

 
@implementation PermutationEnumerator 
 
- (id)initWithArray:(NSArray *)anArray 
{ 
    int index; 
 
    [super init]; 
 
    if(!(count = [anArray count])){ 
        [NSException raise:NSInvalidArgumentException 
                      format:@”can’t_permute_zero_items”]; 
    } 
    array = anArray; [array retain]; 
 
    swapLocs = NSZoneMalloc(NSDefaultMallocZone(), 
                             count*sizeof(int)); 
    for(index=0; index<count; index++){ 
        swapLocs[index] = 0; 
    } 
 
    done = NO; 
 
    return self; 
}

The initializer raises an exception if the array is empty. Otherwise the array is retained by the enumerator. We allocate the array for the individual digits in the next call. (Note that we could have used an integer and extracted the individual digits as necessary, by a process that is precisely like converting an integer to binary. Unfortunately this would limit our enumerator to arrays with at most m items, where m is the largest value such that m! can be represented in a machine integer.) We start counting at zero, and hence all the digits are set to zero.

 
- (id)nextObject 
{ 
    NSMutableArray *result; 
 
    int index; 
    if(done==YES){ 
        return nil; 
    } 
 
    result = [NSMutableArray arrayWithArray:array]; 
    for(index=0; index<count; index++){ 
        int upper = count-1-index; 
        if(swapLocs[index]!=upper){ 
            [result exchangeObjectAtIndex:swapLocs[index] 
                     withObjectAtIndex:upper]; 
        } 
    } 
 
    for(index=count-1; index>=0; index--){ 
        if(swapLocs[index]<count-1-index){ 
            swapLocs[index]++; 
            while(++index<count){ 
                swapLocs[index] = 0; 
            } 
            break; 
        } 
    } 
    if(index<0){ 
        done = YES; 
    } 
 
    return result; 
}

The method nextObject: constructs the permutation that corresponds to the current value of the counter and increments it. The first digit tells us which of the n items to choose for the last position, the second digit which to choose for the next-to-last position and so on. We increment the counter by scanning digits from the right until we find a digit that is not maximal, and increment it. Digits to the left of this digit are set to zero. We are done if all digits are maximal. The result was created with arrayWithArray:, so it is autoreleased.

 
- (void)dealloc 
{ 
    [array release]; 
    NSZoneFree(NSDefaultMallocZone(), swapLocs); 
    [super dealloc]; 
} 
 
@end 
 
@interface NSArray (Permute) 
 
- (NSEnumerator *)permutationEnumerator; 
 
@end 
 
@implementation NSArray (Permute) 
 
- (NSEnumerator *)permutationEnumerator 
{ 
    NSEnumerator *en = 
        [[PermutationEnumerator alloc] initWithArray:self]; 
    [en autorelease]; 
    return en; 
} 
 
@end

The remaining code assures that the buffer for the digits is freed properly when the enumerator is deallocated and adds a method to NSArray that returns an autoreleased permutation enumerator for the contents of the array. This algorithm is based on the random-permutation algorithm from The Art of Computer Programming.

1.2.3 Remark

We can dispense with the array of digits if the number of permutations fits into an unsigned long integer. This simplifies the algorithm quite a lot, since we need only convert the counter value into the factorial base.

The function permute extracts factorial base digits one by one and swaps the appropriate element to the current end of the permutation, where it will remain. The end moves from the top of the array to the bottom.

 
#include <stdio.h> 
#include <string.h> 
 
unsigned long factorial(n) 
{ 
    return (n <= 1 ? 1 : n*factorial(n-1)); 
} 
 
void permute(char **perm, unsigned long p, int n) 
{ 
    int pos; 
 
    for(pos=n; pos>0; pos--){ 
        int s = p % pos; 
        p = (p-s)/pos; 
 
        if(s<pos){ 
            char *temp; 
 
            temp = perm[pos-1]; 
            perm[pos-1] = perm[s]; 
            perm[s] = temp; 
        } 
    } 
}

The loop at the heart of the program counts from zero to n! - 1.

 
int main(int argc, char** argv, char **env) 
{ 
    if(argc<2){ 
        printf(”need_at_least_one_item_to_permute\n”); 
        exit(1); 
    } 
 
    int n=argc-1; 
    char **perm = (char **)malloc(n*sizeof(char *)); 
 
    unsigned long p, mx = factorial(n); 
    for(p=0; p<mx; p++){ 
        memcpy(perm, argv+1, n*sizeof(char *)); 
        permute(perm, p, n); 
 
        int pos; 
        printf(”%s”, perm[0]); 
        for(pos=1; pos<n; pos++){ 
            printf(”_%s”, perm[pos]); 
        } 
        putchar(\n’); 
    } 
 
    free(perm); 
 
    exit(0); 
}