Counting I: Subset enumerator

The goal is to enumerate all subsets of some set of elements stored in an array. It is true for any such subset that an original element from the array is either present or absent. This means that we can enumerate subsets by counting in binary from 0 to 2ⁿ - 1, where n is the number of elements in the array. If bit k is set, then we include the element at k, otherwise it is left out. We could use machine integers to count to 2ⁿ - 1, but then the size of a machine integer would limit the size of the array whose subsets we wish to enumerate.

1.1.2 Implementation

@interface SubsetEnumerator : NSEnumerator
{
    NSArray *array;
    char *binary;
    int count;
    BOOL done;
}

- (id)initWithArray:(NSArray *)anArray;
- (id)nextObject;
- (void)dealloc;

@end

The state of the enumerator is defined by the array whose subsets we wish to enumerate, the number of elements in the array, an array that stores the binary digits of the counter and a flag that indicates whether we are done.

@implementation SubsetEnumerator

- (id)initWithArray:(NSArray *)anArray
{
    int index;

    [super init];

    count = [anArray count];
    array = anArray; [array retain];

    binary = NSZoneMalloc(NSDefaultMallocZone(),
                           count*sizeof(char));
    for(index=0; index<count; index++){
        binary[index] = 0;
    }

    done = NO;

    return self;
}

The enumerator retains the array. We store the number of elements in the instance variable count for easy reference. We allocate space for the binary digits of the counter and set them all to zero.

- (id)nextObject
{
    NSMutableArray *result;

    int index;
    if(done==YES){
        return nil;
    }

    result = [NSMutableArray arrayWithCapacity:1];
    for(index=0; index<count; index++){
        if(binary[index]){
            [result
                addObject:
                     [array objectAtIndex:index]];
        }
    }

The first part of nextObject computes the current subset. It checks every binary digit and includes the corresponding item if the bit is set.

    for(index=count-1; index>=0; index--){
        if(!binary[index]){
            binary[index]++;
            while(++index<count){
                binary[index] = 0;
            }
            break;
        }
    }
    if(index<0){
        done = YES;
    }

    return result;
}

The second part increments the counter, i.e. it implements binary addition. Scan from the right until you find a zero digit, increment this digit and set remaining positions to zero. We are done enumerating when there is no zero digit, and indicate this by setting the flag done. The result was created with arrayWithCapacity:, so it is autoreleased.

- (void)dealloc
{
    [array release];
    NSZoneFree(NSDefaultMallocZone(), binary);
    [super dealloc];
}

@end

@interface NSArray (Subsets)

- (NSEnumerator *)subsetEnumerator;

@end

@implementation NSArray (Subsets)

- (NSEnumerator *)subsetEnumerator
{
    NSEnumerator *en =
        [[SubsetEnumerator alloc] initWithArray:self];
    [en autorelease];
    return en;
}

@end

It remains to clean up: free the buffer that holds the binary digits and release the array (this matches the retain from initWithArray.) We put the method subsetEnumerator into a category. The subset enumerator is autoreleased.

You may find yourself wanting to sort subsets according to the number of elements if you use this category. This is done with

int acountcmp(id a1, id a2, void *context)
{
    int v1 = [a1 count];
    int v2 = [a2 count];
    if (v1 < v2)
        return NSOrderedAscending;
    else if (v1 > v2)
        return NSOrderedDescending;
    else
        return NSOrderedSame;
}

    en = [args subsetEnumerator];
    all = [[en allObjects]
              sortedArrayUsingFunction:acountcmp
              context:NULL];

1.1.3 Remark

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

The function subset extracts binary digits one by one and includes an element if the corresponding digit is one. The elements of the subset are collected at the front of the array, and the remaining locations are marked with a NULL pointer.

#include <stdio.h>
#include <string.h>

void subset(char **subs, unsigned long p, int n)
{
    int pos, dest = 0;

    for(pos=0; pos<n; pos++){
        int s = p % 2;
        p = (p-s)/2;

        if(s){
            subs[dest++] = subs[pos];
        }
    }

    while(dest<n){
        subs[dest++] = NULL;
    }
}

int main(int argc, char** argv, char **env)
{
    if(argc<2){
        printf(”need_at_least_one_item_to_form_set\n”);
        exit(1);
    }

    int n=argc-1;
    char **subs = (char **)malloc(n*sizeof(char *));

    unsigned long p, mx = 1<<n;
    for(p=0; p<mx; p++){
        memcpy(subs, argv+1, n*sizeof(char *));
        subset(subs, p, n);

        putchar(’[’);
        int pos;
        for(pos=0; pos<n; pos++){
            if(subs[pos]==NULL){
                break;
            }
            if(pos){
                putchar(’_’);
            }
            printf(”%s”, subs[pos]);
        }
        puts(”]”);
    }

    free(subs);

    exit(0);
}

1.1 Counting I: Subset enumerator

1.1.1 Idea

1.1.2 Implementation

1.1.3 Remark