生成NSArray元素的排列 [英] Generating permutations of NSArray elements

问题描述

让我们假设我有一个NSNumbers NSArray这样：1，2，3

Let's say I have an NSArray of NSNumbers like this: 1, 2, 3

然后所有可能的排列组合看起来像这样：

Then the set of all possible permutations would look something like this:

1，2，3

1, 2, 3

1，3，2

2，1，3

2，3，1

3 ，1，2

3，2，1

在objective-c中这样做的方法？

What's a good way to do this in objective-c?

推荐答案

我使用了Wevah的答案上面的代码，

I have used the code from Wevah's answer above and discovered some problems with it so here my changes to get it to work properly:

NSArray+Permutation.h

@interface NSArray(Permutation)

- (NSArray *)allPermutations;

@end

NSArray + Permutation.m

NSArray+Permutation.m

#import "NSArray+Permutation.h"

#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 *)allPermutations
{
    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;
}

@end

这篇关于生成NSArray元素的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！