(код ниже относительно моего вопроса)
За этот вопрос о переполнении стека Я использовал подход Пеголона для генерации всех возможных перестановок группы символов внутри строки NSString.Однако сейчас я пытаюсь заставить его не просто генерировать ANAGRAM, который представляет собой все перестановки одинаковой длины, но и все возможные комбинации (любой длины) символов в строке.
Кто-нибудь знает, как яизменит следующий код, чтобы заставить это сделать это?Это очень похоже на: Генерация всех перестановок любой длины - но (из-за страха, что им нужен ответ на домашнюю работу) они не оставили код.У меня есть пример того, что я думал сделать в нижней части этого поста ... но это не так.
Итак, код, как есть, генерирует the, teh, hte, het, eth и eht при получении THE.Что мне нужно, так это: t, h, e, th, ht, te, he (и т. Д.) В дополнение к вышеуказанным 3 комбинациям символов.
Как бы я изменил это, пожалуйста.(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
Как видите, ни одного, ни двух буквенных слов - я выдергиваю волосы!(и у меня не так много свободного!)