Objective-C中的排列/字谜 - 我遗漏了一些东西

Question

(以下关于我的问题的代码)

根据这个堆栈溢出问题,我使用Pegolon的方法生成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

正如你所看到的,没有一两个字母的单词 - 我正在拔我的头发!(而且我没有太多的余地!)

Answer 1

一个简单的方法是获取所有大小的子集k并使用您必须生成子集的所有排列的代码。这很容易，但不是最有效的。

这是一个更好的方法。您在第一个例程中按字典顺序生成排列：

1234
1243
1324
1342
1423
...

每次调用 时NSInteger *pc_next_permutation(NSInteger *perm, const NSInteger size)，您都会通过找到要更改的正确位置来按词法顺序获得下一个排列。当您这样做时，从您更改的位置截断以获得以下内容：

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。