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

Question

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

根据 this stack overflow question我使用 Pegolon 的方法来生成 NSString 中一组字符的所有可能排列。但是，我现在试图让它不仅生成一个 ANAGRAM，它是所有相同长度的排列，而是字符串中字符的所有可能组合(任何长度)。

谁知道我将如何更改以下代码以使其执行此操作？这很像:Generate All Permutations of All Lengths -- 但是(因为害怕他们需要回答作业)他们没有留下代码。我在这篇文章的底部有一个我认为可以做到的示例……但事实并非如此。

因此，代码按原样生成the、teh、hte、het、eth 和 eht 当给定 THE 时。我需要的是:t,h,e,th,ht,te,he (etc) 除了上述 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) 时，您都会通过找到要更改的正确位置来获得 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 的输入应该是 nextPerms 输出的 lastObject。