4
\$\begingroup\$

This algorithm seeks to find all of the possible permutations of a word:

-(void)permute:(NSMutableArray*)word position:(int)p length:(int)l{
    if(p==l){
     [self.allPermutations addObject:[word componentsJoinedByString:@""]];
    } 
    else {
    for(int i = p;i<l;i++){
        NSString* t;
        t= word[p];
        word[p] = word[i];
        word[i] = t;
        [self permute:word position:p+1 length:l];
        t= word[p];
        word[p] = word[i];
        word[i] = t; 
        }
    }
}

After that, I clean out the duplicates with this:

NSArray *cleanedArray = [[NSSet setWithArray:self.allPermutations] allObjects];

This starts to show a lag when the words get to 9 letters or greater. 9 letters is 362,880 loops. Any tips to get this down, or speed up this algorithm in a different way?

\$\endgroup\$
  • \$\begingroup\$ Is this an array of strings containing only single characters? Or is this intended to permute an array of anything? \$\endgroup\$ – nhgrif Jul 18 '14 at 22:01
  • 1
    \$\begingroup\$ I echo nhgrif's question... if the array elements are single characters, this implementation is really overkill. You should use an NSMutableString, or just a C string, in that case. You could improve the question by adding sample code that calls your permute method. \$\endgroup\$ – GraniteRobert Jul 18 '14 at 23:44
8
\$\begingroup\$

Before I comment on performance, I want to comment on style and naming and such.

First and foremost, let's not use single letters for variables. They're meaningless. It's hard to follow what's happening in your code when it's just a handful of letters. Longer variable names has ZERO impact on the runtime performance of your code, but makes a massive difference in the readability and maintainability of your code.

But the thing is, we don't even need the p or l variables. There's an existing Foundation struct design for EXACTLY this purposes. It's called NSRange, which consists of two components, a location (what you're calling p) and a length (what you're calling l).

So, let's change the method name to:

- (void)permute:(NSMutableArray *)word range:(NSRange)range;

Now let's fix the internals of the method. As a note, the following doesn't change any of the logic. It just fixes up the spacing and naming to make the method more readable:

- (void)permute:(NSMutableArray *)word range:(NSRange)range {
    if (range.location == range.length) {
        [self.allPermutations addObject:[word componentsJoinedByString:@""]];
    } else {
        for (int i = range.location; i < range.length; ++i) {
            NSString *currentWord = word[range.location];
            word[range.location] = word[range.length];
            word[range.length] = currentWord;

            [self permute:word range:NSMakeRange(range.location + 1, range.length)];

            currentWord = word[range.location];
            word[range.location] = word[range.length];
            word[range.length] = currentWord;
        }
    }
}

Now the code is a bit more readable without having sacrificed any readability.


But there are still problems.

First of all, why are we using NSString within the loop? It doesn't make any sense. We're not calling any methods on these objects, we're just swapping them around. Instead of NSString, why not just id?

Second, what happens if p is greater than word.count? What happens if l + p is greater than word.count? What happens if p is negative? What happens if l is negative? A crash happens--that's what. If you want this method to find all permutations, then start by having an outer method which takes only an NSMutableArray argument and then calls a method that looks like this but the first call it send an NSRange object with a location of 0 and a length of word.count.


Here's another issue:

    [self permute:word position:p+1 length:l];
    t= word[p];
    word[p] = word[i];
    word[i] = t; 

Are these last 3 lines ever executed in a meaningful way? If you comment every non-brace line after the recursive call out, do the results change? By the time you get to these three lines, you've already executed

[self.allPermutations addObject:[word componentsJoinedByString:@""]];

As far as I can tell, all those last three lines might be doing is straightening the array back out into its original form... is that the intent here? That's crazy to have this many executions of code on the way out of the recursive call just to straighten a mutable array out back to its original form, and there's a much better way to do that!

Perhaps I'm misunderstanding the purpose of these three lines, but if I'm understanding this correctly and the only purpose truly is to rewind the array back to it's original position, then let's try this:

- (void)permute:(NSMutableArray *)word range:(NSRange)range {
    static NSMutableArray *copyOfWord;
    if (!copyOfWord) {
        copyOfWord = [word copy];
    }
    if (range.location == range.length) {
        [self.allPermutations addObject:[copyOfWord componentsJoinedByString:@""]];
        copyOfWord = nil; // We're done now.  Set back to `nil` so next call can use it
    } else {
        for (int i = range.location; i < range.length; ++i) {
            NSString *currentWord = copyOfWord[range.location];
            copyOfWord[range.location] = copyOfWord[range.length];
            copyOfWord[range.length] = currentWord;

            [self permute:copyOfWord range:NSMakeRange(range.location + 1, range.length)];
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.