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.
因此,代码生成
, teh
, hte
,给予
THE $时,
, eth
和 eht
C $ C>。
我需要的是: t
, h
, e
,个
, HT
,叔
,他
(等)以及上述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
:
#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 $ c $输出的
lastObject
C>。
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屋!