Permutations/Anagrams in Objective-C -- I am missing something

Question

(code below regarding my question)

Per this stack overflow question I used Pegolon's approach to generating all possible permutations of a group of characters inside an NSString. However, I am now trying to get it to not just generate an ANAGRAM which is all permutations of the same length, but all possible combinations (any length) of the characters in a string.

Would anyone know how i would alter the following code to get it to do this? This is much like: Generate All Permutations of All Lengths -- but (for fear of them needing answer to homework) they did not leave code. I have a sample of what I thought would do it at the bottom of this post... but it did not.

So, the code, as is, generates the, teh, hte, het, eth and eht when given THE. What I need is along the lines of: t,h,e,th,ht,te,he (etc) in addition to the above 3 character combinations.

How would I change this, please. (ps: There are two methods in this. I added allPermutationsArrayofStrings in order to get the results back as strings, like I want them, not just an array of characters in another array). I am assuming the magic would happen in pc_next_permutation anyway -- but thought I would mention it.

In NSArray+Permutation.h

#import <Foundation/Foundation.h>

@interface NSArray(Permutation)
- (NSArray *)allPermutationsArrayofArrays;
- (NSArray *)allPermutationsArrayofStrings;

@end

in NSArray+Permutation.m:

#define MAX_PERMUTATION_COUNT   20000

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

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

    assert(pos1 >= 0 && pos1 <= size);

    NSInteger pos2;
    // slide down the array looking for a bigger number than what we found before
    for (pos2 = size; perm[pos2] <= perm[pos1] && pos2 > 0; --pos2);

    assert(pos2 >= 0 && pos2 <= size);

    // swap them
    NSInteger tmp = perm[pos1]; perm[pos1] = perm[pos2]; perm[pos2] = tmp;

    // now reverse the elements in between by swapping the ends
    for (++pos1, pos2 = size; pos1 < pos2; ++pos1, --pos2) {
        assert(pos1 >= 0 && pos1 <= size);
        assert(pos2 >= 0 && pos2 <= size);

        tmp = perm[pos1]; perm[pos1] = perm[pos2]; perm[pos2] = tmp;
    }

    return perm;
}

@implementation NSArray(Permutation)

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

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

    NSInteger permutationCount = 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)) && ++permutationCount < MAX_PERMUTATION_COUNT);
    free(perm);

    return perms;
}

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

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

    NSInteger permutationCount = 0;

    --size;

    NSMutableArray *perms = [NSMutableArray array];

    do {
        NSMutableString *newPerm = [[[NSMutableString alloc]initWithString:@"" ]autorelease];

        for (NSInteger i = 0; i <= size; ++i)
        {
            [newPerm appendString:[self objectAtIndex:perm[i]]];
        }
        [perms addObject:newPerm];
    } while ((perm = pc_next_permutation(perm, size)) && ++permutationCount < MAX_PERMUTATION_COUNT);
    free(perm);

    return perms;
}

@end

My code that I thought would fix this:

for ( NSInteger i = 1; i <= theCount; i++) {
                NSRange theRange2;
                theRange2.location = 0;
                theRange2.length = i;
                NSLog(@"Location: %i (len: %i) is: '%@'",theRange2.location,theRange2.length,[array subarrayWithRange:theRange2]);

                NSArray *allWordsForThisLength = [[array subarrayWithRange:theRange2] allPermutationsArrayofStrings];
                for (NSMutableString *theString in allWordsForThisLength)
                {
                    NSLog(@"Adding %@ as a possible word",theString);
                    [allWords addObject:theString];
                }

I know it would not be the most efficient..but I was trying to test.

This is what I got:

2011-07-07 14:02:19.684 TA[63623:207] Total letters in word: 3
2011-07-07 14:02:19.685 TA[63623:207] Location: 0 (len: 1) is: '(
    t
)'
2011-07-07 14:02:19.685 TA[63623:207] Adding t as a possible word
2011-07-07 14:02:19.686 TA[63623:207] Location: 0 (len: 2) is: '(
    t,
    h
)'
2011-07-07 14:02:19.686 TA[63623:207] Adding th as a possible word
2011-07-07 14:02:19.687 TA[63623:207] Adding ht as a possible word
2011-07-07 14:02:19.688 TA[63623:207] Location: 0 (len: 3) is: '(
    t,
    h,
    e
)'
2011-07-07 14:02:19.688 TA[63623:207] Adding the as a possible word
2011-07-07 14:02:19.689 TA[63623:207] Adding teh as a possible word
2011-07-07 14:02:19.690 TA[63623:207] Adding hte as a possible word
2011-07-07 14:02:19.691 TA[63623:207] Adding het as a possible word
2011-07-07 14:02:19.691 TA[63623:207] Adding eth as a possible word
2011-07-07 14:02:19.692 TA[63623:207] Adding eht as a possible word

As you can see, no one or two letter words -- I am pulling my hair out! (and I don't have much to spare!)

Answer 1

An easy thing to do would be to take all subsets of size k and use the code you have to generate all permutations of the subset. This is easy, but not the most efficient.

---

Here's a better approach. You are generating permutations lexicographically in the first routine:

1234
1243
1324
1342
1423
...

Each time you call NSInteger *pc_next_permutation(NSInteger *perm, const NSInteger size), you get the next permutation in lex order by finding the correct position to change. When you do that, truncate from the spot you changed to get the following:

1234 123 12 1
1243 124
1324 132 13
1342 134
1423 142 14
1432 143
2143 214 21 2
...

I hope the idea is clear. Here's one way to implement this (in Objective C-like pseudocode).

-(NSMutableArray *)nextPerms:(Perm *)word {
    int N = word.length;
    for (int i=N-1; i > 0; ++i) {
        if (word[i-1] < word[i]) {
            break;
        } else if (i==1) {
            i = 0;
        }
    }
    // At this point, i-1 is the leftmost position that will change
    if (i == 0) {
        return nil;
    }
    i = i-1;
    // At this point, i is the leftmost position that will change
    Perm *nextWord = word;
    for (int j=1; j <= N-i; ++j) {
        nextWord[i+j] = word[N-j];
    }
    nextWord[i] = nextWord[i+1];
    nextWord[i+1] = word[i];

    // At this point, nextPerm is the next permutation in lexicographic order.    

    NSMutableArray *permList = [[NSMutableArray alloc] init];
    for (int j=i; j<N; ++j) {
        [permList addObject:[nextWord subwordWithRange:NSMakeRange(0,i)]];
    }
    return [permList autorelease];
}

This will return an array with the partial permutations as described above. The input for nextPerms should be the lastObject of the output of nextPerms.

Answer 2

Okay,

Down and dirty for now, however, this is what I did...

I changed the NSArray+Permutations.m to be as follows:

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

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

    NSInteger permutationCount = 0;

    --size;

    NSMutableArray *perms = [NSMutableArray array];
    NSMutableDictionary *permsDict = [[NSMutableDictionary alloc] init];

    do {
        NSMutableString *newPerm = [[[NSMutableString alloc]initWithString:@"" ]autorelease];

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

        if ([permsDict objectForKey:newPerm] == nil)
        {
            [permsDict setObject:@"1" forKey:newPerm];
            [perms addObject:newPerm];
        }

        for (NSInteger i = 1; i <= [newPerm length]; ++i)
        {
            NSRange theRange;
            theRange.location = 0;
            theRange.length = i;
            if ([permsDict objectForKey:[newPerm substringToIndex:i]] ==  nil)
            {
                [permsDict setObject:@"1" forKey:[newPerm substringToIndex:i]];
                [perms addObject:[newPerm substringToIndex:i]];
            }
        }

    } while ((perm = pc_next_permutation(perm, size)) && ++permutationCount < MAX_PERMUTATION_COUNT);
    free(perm);

    [permsDict release];

    return perms;
}

The major changes were the idea @PengOne had... Return the resulting lexically changed string but also shorten it by 1 character at a time and add that to the returned array if it did not exist already.

I chose to be "cheap" about it and keep track using a NSMutableDictionary. So if the lexically changed string was not listed in the dictionary, it was added.

Is that more-or-less what you thought I should do, @PengOne?

WAY faster than adding them all and dealing with the resulting duplicates later -- and I think it works like I need it to.