objective-c - 计算数字数组的可能排列

Question

我有一个带有数字 {0,1,2,3} 的 NSArray

计算 4 的阶乘（数组的计数），我有 0、1、2、3 的 24 种可能排列

我想知道是否有办法计算所有这些可能的排列并将它们放在一个单独的数组中。

例如，给定上面的数字 {0,1,2,3}，得到的排列将是：

0123, 0132, 0213, 0231, 0312, 0321,
1023, 1032, 1203, 1230, 1302, 1320,
2013, 2031, 2103, 2130, 2301, 2310,
3012, 3021, 3102, 3120, 3201, 3210

任何帮助是极大的赞赏。非常感谢！

Answer 1

我想知道是否有办法计算所有这些可能的排列

当然（尽​​管它们不是组合，而是排列）：

unsigned long long factorial(unsigned long long n)
{
    return n > 1 ? n * factorial(n - 1) : 1;
}

unsigned long long perms = factorial(array.count);

并将它们放在一个单独的数组中。

当然，也有很好的排列算法，例如Johnson-Trotter 算法。

Answer 2

我一直在寻找代码，但我设法弄清楚了:) 如果其他人需要它，代码如下：

static NSMutableArray *results;

void doPermute(NSMutableArray *input, NSMutableArray *output, NSMutableArray *used, int size, int level) {
    if (size == level) {
        NSString *word = [output componentsJoinedByString:@""];
        [results addObject:word];
        return;
    }

    level++;

    for (int i = 0; i < input.count; i++) {
        if ([used[i] boolValue]) {
            continue;
        }

        used[i] = [NSNumber numberWithBool:YES];
        [output addObject:input[i]];
        doPermute(input, output, used, size, level);
        used[i] = [NSNumber numberWithBool:NO];
        [output removeLastObject];
    }
}

NSArray *getPermutations(NSString *input, int size) {
    results = [[NSMutableArray alloc] init];

    NSMutableArray *chars = [[NSMutableArray alloc] init];


    for (int i = 0; i < [input length]; i++) {
        NSString *ichar  = [NSString stringWithFormat:@"%c", [input characterAtIndex:i]];
        [chars addObject:ichar];
    }

    NSMutableArray *output = [[NSMutableArray alloc] init];
    NSMutableArray *used = [[NSMutableArray alloc] init];

    for (int i = 0; i < chars.count; i++) {
        [used addObject:[NSNumber numberWithBool:NO]];
    }

    doPermute(chars, output, used, size, 0);

    return results;
}

采用

getPermutations（输入，大小）

得到一个存储了排列的 NSArray。

例如：

NSLog(@"%@", getPermutations(@"0123", 4));

//console log
RESULTS: (
    0123,
    0132,
    0213,
    0231,
    0312,
    0321,
    1023,
    1032,
    1203,
    1230,
    1302,
    1320,
    2013,
    2031,
    2103,
    2130,
    2301,
    2310,
    3012,
    3021,
    3102,
    3120,
    3201,
    3210
)

它现在对我来说很完美:)