Objective-C 中的排列/字谜——我遗漏了一些东西 [英] Permutations/Anagrams in Objective-C -- I am missing something
问题描述
(下面关于我的问题的代码)
(code below regarding my question)
根据 这个堆栈溢出问题我使用 Pegolon 的方法来生成所有可能的排列NSString 中的一组字符.但是，我现在试图让它不仅生成一个 ANAGRAM，它是所有相同长度的排列，而且是字符串中字符的所有可能组合(任何长度).
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.
因此，代码按原样生成 the、teh、hte、het、eth 和 eht 当给定 THE 时.我需要的是:t,h,e,th,ht,te,he (etc) 除了以上 3 个字符组合.
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.
请问我该如何更改.(ps:这里有两种方法.我添加了 allPermutationsArrayofStrings 以便将结果作为字符串返回，就像我想要的那样，而不仅仅是另一个数组中的字符数组).我假设魔法会发生在 pc_next_permutation 中——但我想我会提到它.
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.
在 NSArray+Permutation.h 中
In NSArray+Permutation.h
#import <Foundation/Foundation.h>
@interface NSArray(Permutation)
- (NSArray *)allPermutationsArrayofArrays;
- (NSArray *)allPermutationsArrayofStrings;
@end
在 NSArray+Permutation.m 中:
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.
这是我得到的:
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!)
推荐答案
一个简单的方法是获取所有大小为 k 的子集并使用您必须生成的所有排列的代码子集.这很简单，但不是最有效的.
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
...
每次调用 NSInteger *pc_next_permutation(NSInteger *perm, const NSInteger size) 时，您都会通过找到要更改的正确位置来获得按 lex 顺序排列的下一个排列.当您这样做时，从您更改的位置截断以获得以下内容:
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
...
我希望这个想法很清楚.这是实现这一点的一种方法(在类似于 Objective C 的伪代码中).
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];
}
这将返回一个具有上述部分排列的数组.nextPerms 的输入应该是 nextPerms 输出的 lastObject.
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.
这篇关于Objective-C 中的排列/字谜——我遗漏了一些东西的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
