目标中的排列/ Anagrams
（代码如下关于我的问题）
根据这个堆栈溢出问题，我使用Pegolon的方法来生成NSString中一组字符的所有可能的排列组合。 不过，我现在试图让它不仅仅生成一个ANAGRAM，它是所有长度相同的排列，而是字符串中所有可能的字符组合（任何长度）。
有谁知道我会如何改变下面的代码来实现它？ 这很像：生成所有长度的所有排列 - 但（因为担心他们需要回答作业），他们没有留下代码。 我有一个我认为会在这篇文章底部做到的样本......但事实并非如此。
所以，代码，按原样产生the ， teh ， hte ， het ， eth和eht时给出THE 。 除了上述3个字符组合外，我需要的是： t ， h ， e ， th ， ht ， te ， he （等）。
请问我该如何改变这一点。 （ps：这里有两个方法，我添加了allPermutationsArrayofStrings以便将结果返回为字符串，就像我想要的那样，而不仅仅是另一个数组中的字符数组）。 无论如何，我假设魔法会在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];
}
我知道这不会是最有效的..但我试图测试。
这就是我得到的：
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) ，通过查找正确的位置来更改lex顺序中的下一个排列。 当你这样做时，从你更改的地方截断以获得以下内容：
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 <= 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];
}
这将返回如上所述的具有部分排列的数组。 nextPerms的输入应该是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的想法...返回由此产生的词法改变的字符串，但是也一次缩短1个字符，并且将其添加到返回的数组中，如果它不存在的话。
我选择了“便宜”，并使用NSMutableDictionary跟踪。 所以如果字典中没有列出词法改变的字符串，它就会被添加。
@PengOne是多少还是你认为我应该做的？
WAY比将它们全部添加并稍后处理所产生的重复项更快 - 我认为它可以像我需要的那样工作。
链接地址: http://www.djcxy.com/p/53503.html