Permutations/Anagrams in Objective
(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!)
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 .
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.
链接地址: http://www.djcxy.com/p/53504.html上一篇: 詹金斯检出一个新的工作区
下一篇: 目标中的排列/ Anagrams