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

Question

(code below regarding my question)

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

Does anyone know how I would modify the following code to make it do this? This is very similar to: Generate All Permutations of All Lengths - but (fearing that they need an answer to their homework), they didn’t leave the code. I have a sample of what I thought would do it at the bottom of this article ... but it is not.

Thus, the code, as is, generates the , teh , hte , het , eth and eht when specifying the . I need the following lines: t , h , e , th , ht , te , he (etc.) In addition to the above 3 character combinations.

How to change this, please. (ps: There are two methods to this. I added allPermutationsArrayofStrings to return the results as strings, for example, I want them, and not just an array of characters in another array). I assume that magic will happen in pc_next_permutation anyway - but I thought I mentioned 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, which 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 that this would not be the most effective ... but I tried to check.

Here 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, not a single, not two literal words - I pull out my hair! (and I have nothing to save!)

Answer 1

It would be easy to make all subsets of size k and use the code that you should generate all permutations of the subset. It is easy, but not the most effective.

---

Here's the best approach. You generate permutations lexicographically in the first procedure:

 1234 1243 1324 1342 1423 ... 

Each time you call NSInteger *pc_next_permutation(NSInteger *perm, const NSInteger size) , you get the following permutation in lex order, finding the correct position to change. When you do this, crop from the place 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 the Objective-C-like pseudo-code).

 -(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 <= Ni; ++j) { nextWord[i+j] = word[Nj]; } 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 partial permutations, as described above. The input for nextPerms should be the lastObject output.

Answer 2

Good,

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

I modified NSArray+Permutations.m 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 main changes were in the idea of ​​@PengOne ... Return the resulting lexically modified string, but also shorten it by 1 character at a time and add it to the returned array, if it does not already exist.

I decided to be “cheap” about it and track using NSMutableDictionary . Therefore, if a lexically modified line is not specified in the dictionary, it was added.

Is this more or less what you think is necessary, @PengOne?

WAY is faster than adding them all, and later process the resulting duplicates - and I think it works the way I need.