Objective-C中的排列/ Anagrams – 我错过了一些东西
（以下代码关于我的问题）
根据这个堆栈溢出问题，我使用Pegolon的方法来生成NSString中一组字符的所有可能的排列组合。 不过，我现在试图让它不只是生成一个ANAGRAM，它是所有长度相同的排列，而是一个string中所有可能的字符组合（任意长度）。
有谁知道我会如何改变下面的代码来做到这一点？ 这很像： 生成所有长度的所有排列 – 但是（因为担心他们需要回答作业），他们没有留下代码。 我有一个我认为会在这篇文章底部做的样本…但是没有。
所以，这个代码就是在给定THE时产生，并且产生， het ， eth和eht 。 除了上述3个字符组合之外，我需要的是： t ， h ， e ， th ， ht ， te ， he （等等）。
我将如何改变这一点，请。 （ps：这里有两个方法，我添加了allPermutationsArrayofStrings为了得到结果回来的string，就像我想要他们，不只是在另一个数组中的字符数组）。 我假设魔法会发生在pc_next_permutation – 但是我想我会提到它。
在NSArray + Permutation.h中
#import <Foundation/Foundation.h> @interface NSArray(Permutation) - (NSArray *)allPermutationsArrayofArrays; - (NSArray *)allPermutationsArrayofStrings; @end
在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
我认为我的代码将解决这个问题：
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]; }
我知道这不会是最有效的..但我试图testing。
这是我得到的：
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
正如你所看到的，没有一个或两个字母的词 – 我拉我的头发！ （我没有太多的空余！）
一个容易做的事情就是取所有大小为k子集，并使用代码来生成子集的所有排列。 这很容易，但不是最有效的。
这是一个更好的方法。 您在第一个例程中按字典顺序生成排列：
1234 1243 1324 1342 1423 ...
每次调用NSInteger *pc_next_permutation(NSInteger *perm, const NSInteger size) ，通过find正确的位置来进行下一个sorting。 当你这样做的时候，从你改变的地方截断，得到以下结果：
1234 123 12 1 1243 124 1324 132 13 1342 134 1423 142 14 1432 143 2143 214 21 2 ...
我希望这个想法很清楚。 这里有一个方法来实现这个（在Objective-C中的伪代码）。
-(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]; }
这将返回如上所述的具有部分排列的数组。 nextPerms的input应该是lastObject输出的nextPerms 。
好的，
但是，这是我做的…
我改变了NSArray+Permutations.m如下：
- (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; }
主要的变化是@PengOne的想法…返回由此产生的词法改变的string，但也一次缩短1个字符，并添加到返回的数组，如果它不存在已经。
我select了“便宜”，并跟踪使用NSMutableDictionary 。 所以如果字典中没有列出词法改变的string，那么它就被添加了。
@PengOne，你认为我应该做什么或多或less？
方式比添加全部和处理所得到的重复更快 – 我认为它的工作就像我需要它。