0%

OC数组排列组合

出租告示

今天上午同事在rtx群里面发了这样一张图片,挺有意思的哈,地球人已经阻止不了程序猿哥了。只要懂一点程序的人都知道这段代码是干什么用的(这应该是java吧),这就是根据index数组里面的值从另外一个数组arr里面读取值,然后组成一个电话号码字符串。

后面的结果电话号码是:18013820100 (ps 貌似这个电话打不通哈)

中午吃饭的时候,想了下,这里 arr 应该有 n! 中可能(n代码电话号码去重后的数字个数),这里就是高中数学的排列组合知识,然后根据 arr 数组确定 index 数组。

画了一张解决思路流程图,其实就像高中数学老师讲的一样,第一位有n种选择,第二位有 n - 1 种选择,以此类推,然后将这种解决方式列举出来,下面就是相关代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
- (void)allPermutationsOfArray:(NSArray *)array {
    // 最终的排列数组
    NSMutableArray *permutations = [NSMutableArray new];
    for (NSInteger i = 0; i < [array count]; i++) {
        if ([permutations count] == 0) {
            for (id item in array ) {
                // 将数组里面的每个元素都作为一个数组
                [permutations addObject:[NSMutableArray arrayWithObject:item]];
            }
        } else {
            NSMutableArray *permutationsCopy = [permutations mutableCopy];
            [permutations removeAllObjects];
            for (id item in array ) {
                for (NSMutableArray *partialList in permutationsCopy) {
                    // 遍历 看已排列的数组里面是否包含 某个元素 如果没包含 则加入该元素 类型于 1->12->123->1234 这个过程 这里的顺序由传入的array元素顺序决定
                    if (![partialList containsObject:item]) {
                        NSMutableArray *partialNewList = [@[] mutableCopy];
                        // 将不包含的元素 加入前面 符合我们的习惯
                        [partialNewList addObject:item];
                        [partialNewList addObjectsFromArray:partialList];
                        
                        [permutations addObject:partialNewList];
                    }
                }
            }
        }
    }
     NSLog(@"permutations count:%@", @(permutations.count));
    [self printArrayInLine:permutations];
}

- (void)printArrayInLine:(NSArray *)twoDimensionArray {
    for (NSArray *array in twoDimensionArray) {
        NSString * result = [[array valueForKey:@"description"] componentsJoinedByString:@""];
        NSLog(@"%@\n",result);
    }
}

- (NSMutableArray *)getIndexArray:(NSMutableArray *)array phone:(NSString *)phone {
__block NSMutableArray *indexArray = [@[] mutableCopy];
[results enumerateObjectsUsingBlock:^(NSString *_Nonnull obj, NSUInteger idx, BOOL *_Nonnull stop) {
[indexArray appendObject:[self indexString:obj phone:phone]];
}];
return indexArray;
}

- (NSString *)indexString:(NSString *)s phone:(NSString *)phone {
NSString *indexString = @"";
NSMutableArray *sArray = [@[] mutableCopy];
NSMutableArray *phoneArray = [@[] mutableCopy];
for (NSInteger i = 0; i < [s length]; i++) {
[sArray addObject:[NSString stringWithFormat:@"%c", [s characterAtIndex:i]]];
}
for (NSInteger i = 0; i < [phone length]; i++) {
[phoneArray addObject:[NSString stringWithFormat:@"%c", [phone characterAtIndex:i]]];
}
for (NSInteger i = 0; i < [phoneArray count]; i++) {
NSUInteger index = [sArray indexOfObject:phoneArray[i]];
indexString = [indexString stringByAppendingString:@(index).stringValue];
}
return indexString;
}

Google search keywords: objective-c array permutation combination factorial 排列 组合 阶乘

上述代码参考链接:
http://stackoverflow.com/questions/15738807/calculate-possible-permutations-of-an-array-of-numbers

感兴趣的还可以看一下下面的链接:
http://stackoverflow.com/questions/15738807/calculate-possible-permutations-of-an-array-of-numbers
http://stackoverflow.com/questions/3791265/generating-permutations-of-nsarray-elements
http://codereview.stackexchange.com/questions/57340/seeking-improved-objective-c-permutation-algorithm
http://stackoverflow.com/questions/6617253/permutations-anagrams-in-objective-c-i-am-missing-something