生成 NSArray 元素的排列

Question

假设我有一个 NSNumbers 的 NSArray，如下所示： 1, 2, 3

那么所有可能的排列的集合将如下所示：

1,2,3

1,3,2

2,1,3

2、3、1

3,1,2

3,2,1

在 Objective-c 中执行此操作的好方法是什么？

Answer 1

我已经使用了上面 Wevah 的答案中的代码，并发现了一些问题，所以在这里我进行了更改以使其正常工作：

NSArray+Permutation.h

@interface NSArray(Permutation)

- (NSArray *)allPermutations;

@end

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

Answer 2

可能有更好的方法来做到这一点（就地或其他方式），但这似乎有效：

Header:

@interface NSArray (PermutationAdditions)

- (NSArray *)allPermutations;

@end

Implemetation:

@implementation NSArray (PermutationAdditions)

NSInteger *pc_next_permutation(NSInteger *p, const NSInteger size) {
    // slide down the array looking for where we're smaller than the next guy
    NSInteger i;
    for (i = size - 1; p[i] >= p[i + 1]; --i) { }

    // if this doesn't occur, we've finished our permutations
    // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
    if (i == -1)
        return NULL;

    NSInteger j;
    // slide down the array looking for a bigger number than what we found before
    for (j = size; p[j] <= p[i]; --j) { }

    // swap them
    NSInteger tmp = p[i]; p[i] = p[j]; p[j] = tmp;

    // now reverse the elements in between by swapping the ends
    for (++i, j = size; i < j; ++i, --j) {
        tmp = p[i]; p[i] = p[j]; p[j] = tmp;
    }

    return p;
}

- (NSArray *)allPermutations {
    NSInteger size = [self count];
    NSInteger *perm = malloc(size * sizeof(NSInteger));

    for (NSInteger idx = 0; idx < size; ++idx)
        perm[idx] = idx;

    NSInteger j = 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)) && ++j);

    return perms;
}

@end

要使用它，只需 #import 头文件，然后调用 [yourArray allPermutations];该方法将返回一个包含每个排列数组的数组。

[代码改编自 PHP 代码此处。]

Answer 3

您可以将 NSString *characters 更改为 id Something 并将其用于任何类型的对象

NSArray *array = [NSArray arrayWithObjects:@"a",@"b",@"c", nil];

NSMutableArray *permutations = nil;

int i = 0;
for (i = 0; i < array.count ; i++){

    if (!permutations){
        permutations = [NSMutableArray array];
        for (NSString *character in array){
            [permutations addObject:[NSArray arrayWithObject:character]];
        }

    } else {

        //make copy of permutations array and clean og array
        NSMutableArray *aCopy = [permutations mutableCopy];
        [permutations removeAllObjects];

        for (NSString *character in array){

            //loop through the copy
            for (NSArray *oldArray in aCopy){

                //check if old string contains looping char.. 
                if ([oldArray containsObject:character] == NO){

                    //update array
                    NSMutableArray *newArray = [NSMutableArray arrayWithArray:oldArray];
                    [newArray addObject:character];

                    //add to permutations
                    [permutations addObject:newArray];

                }

            }
        }            
    }



}
NSLog(@"permutations = \n %@",permutations);

Answer 4

我最近偶然发现了同样的问题，并编写了一个我认为更具可读性的递归解决方案。它依赖于此处所述的核心原理。我将其包含在这里，以防它对某人有帮助：

- (NSMutableArray <NSArray *> *)permutationOfArray:(NSMutableArray *)array withPrefixArray:(NSMutableArray *)prefixArray withPermutations:(NSMutableArray <NSArray *> *)permutations {
    NSUInteger numArrayElements = [array count];
    if (numArrayElements == 0) {
        [permutations addObject:prefixArray];
        return permutations;
    }
    
    for (NSUInteger i = 0; i < numArrayElements; i++) {
        // Remove object and add it to the prefix array.
        // Note: we must create new copies of the arrays as we
        // are running using recursive call and these objects
        // are called by reference.            
        NSMutableArray *newArray = [NSMutableArray arrayWithArray:array];
        [newArray removeObjectAtIndex:i];
        NSMutableArray *newPrefixArray = [NSMutableArray arrayWithArray:prefixArray];
        [newPrefixArray addObject:[array objectAtIndex:i]];
        
        [self permutationOfArray:newArray withPrefixArray:newPrefixArray withPermutations:permutations];
    }
    
    return permutations;
}

- (NSArray <NSArray *> *)allPermutationsOfArray:(NSArray *)array {
    return [self permutationOfArray:[NSMutableArray arrayWithArray:array] withPrefixArray:[NSMutableArray array] withPermutations:[NSMutableArray array]];
}

示例调用：

NSArray <NSArray *> *permutations = [self allPermutationsOfArray:@[@1, @2, @3]];
for (NSArray *singlePermutation in permutations) {
    NSLog(@"%@", [singlePermutation componentsJoinedByString:@", "]);
}

结果：

1,2,3

1,3,2

2,1,3

2、3、1

3,1,2

3,2,1

Answer 5

扩展 SSJ 的答案 -

为了清晰

起见，打印日志 - 适用于任何对象

- 更多解释 -

边缘情况

[self allPermutationsOfArray:@[@1,@2,@3,@4]]; // usage

...

-(void)allPermutationsOfArray:(NSArray*)array
{
    NSMutableArray *permutations = [NSMutableArray new];

    for (int i = 0; i < array.count; i++) { // for each item in the array
        NSLog(@"iteration %d", i);
        if (permutations.count == 0) { // first time only

            NSLog(@"creating initial list");
            for (id item in array) { // create a 2d array starting with each of the individual items
                NSMutableArray* partialList = [NSMutableArray arrayWithObject:item];
                [permutations addObject:partialList]; // where array = [1,2,3] permutations = [ [1] [2] [3] ] as a starting point for all options
            }

        } else { // second and remainder of the loops

            NSMutableArray *permutationsCopy = [permutations mutableCopy]; // copy the original array of permutations
            [permutations removeAllObjects]; // remove all from original array

            for (id item in array) { // for each item in the original list
                NSLog(@"adding item %@ where it doesnt exist", item);

                for (NSMutableArray *partialList in permutationsCopy) { // loop through the arrays in the copy

                    if ([partialList containsObject:item] == false) { // add an item to the partial list if its not already

                        // update a copy of the array
                        NSMutableArray *newArray = [NSMutableArray arrayWithArray:partialList];
                        [newArray addObject:item];

                        // add to the final list of permutations
                        [permutations addObject:newArray];
                    }
                }
            }            
        }
        [self printArrayInLine:permutations];
    }
    NSLog(@"%lu permutations",(unsigned long)permutations.count);
}

-(void)printArrayInLine:(NSArray*)twoDimensionArray
{
    NSString* line = @"\n";
    for (NSArray* array in twoDimensionArray) {
        line = [line stringByAppendingString:@"["];
        for (id item in array) {
            line = [line stringByAppendingString:[NSString stringWithFormat:@"%@,",item]];
        }
        line = [line stringByAppendingString:@"]\n"];
    }
    NSLog(@"%@", line);
}

涵盖错误可能导致输入 @[@1,@2,@3] 的日志输出的

iteration 0
creating initial list
[1,]
[2,]
[3,]
iteration 1
adding item 1 where it doesnt exist and creates a new list
adding item 2 where it doesnt exist and creates a new list
adding item 3 where it doesnt exist and creates a new list
[2,1,]
[3,1,]
[1,2,]
[3,2,]
[1,3,]
[2,3,]
iteration 2
adding item 1 where it doesnt exist and creates a new list
adding item 2 where it doesnt exist and creates a new list
adding item 3 where it doesnt exist and creates a new list
[3,2,1,]
[2,3,1,]
[3,1,2,]
[1,3,2,]
[2,1,3,]
[1,2,3,]
6 permutations