OC数组排列组合

admin

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

后面的结果电话号码是：18013820100 （ps 貌似这个电话打不通哈）

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

画了一张解决思路流程图:

流程图

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

1. - (void)allPermutationsOfArray:(NSArray *)array {
   
2.     // 最终的排列数组
   " k$ l2 l. B6 {3 d- ^
3.     NSMutableArray *permutations = [NSMutableArray new];
   7 `; I, T. ?) ]
4.     for (NSInteger i = 0; i < [array count]; i++) {
   % u# q& U( N  T; R+ H& S
5.         if ([permutations count] == 0) {
   ! k" o8 w% K1 g) k: V1 a6 D2 s
6.             for (id item in array ) {
   
7.                 // 将数组里面的每个元素都作为一个数组
   ) A; U, A" k7 N& _1 C: h
8.                 [permutations addObject:[NSMutableArray arrayWithObject:item]];
   
9.             }
   
10.         } else {
    6 c% l" d# W" ~. n3 N: W, ?
11.             NSMutableArray *permutationsCopy = [permutations mutableCopy];
    / q4 q! U" g. @, w, Z" {
12.             [permutations removeAllObjects];
    ) l/ p5 ^/ D# ^
13.             for (id item in array ) {
    
14.                 for (NSMutableArray *partialList in permutationsCopy) {
    9 g; M8 n' s( ~. |1 L' ^6 Y
15.                     // 遍历 看已排列的数组里面是否包含 某个元素 如果没包含 则加入该元素 类型于 1->12->123->1234 这个过程 这里的顺序由传入的array元素顺序决定
      P+ E6 q! r" b+ [& [3 b
16.                     if (![partialList containsObject:item]) {
    
17.                         NSMutableArray *partialNewList = [@[] mutableCopy];
    
18.                         // 将不包含的元素 加入前面 符合我们的习惯
    " s7 ?$ ^) H: o2 \; F  E
19.                         [partialNewList addObject:item];
    
20.                         [partialNewList addObjectsFromArray:partialList];
    2 X! J- _& }; P
21.                         
    + y7 @' L) R  j7 O, Y3 ?1 |% ]7 G
22.                         [permutations addObject:partialNewList];
    ! s; l0 d+ E% u' Q
23.                     }
    
24.                 }
    
25.             }
    + A+ S2 L9 D! O) P9 ^/ |: u
26.         }
    
27.     }
    : G  J5 m; F: X) K% q
28.      NSLog(@"permutations count:%@", @(permutations.count));
    9 w0 ?  C% S9 O( |8 I: E
29.     [self printArrayInLine:permutations];
    
30. }
      _  {. s1 E' u0 u6 c
31. 
    
32. - (void)printArrayInLine:(NSArray *)twoDimensionArray {
    2 h: N# b3 M4 c( \; R
33.     for (NSArray *array in twoDimensionArray) {
    " |5 H$ b: L& |, f2 [# c7 g
34.         NSString * result = [[array valueForKey:@"description"] componentsJoinedByString:@""];
    ( S+ p  N$ a- g9 _( i' e; v
35.         NSLog(@"%@",result);
    6 |; k/ u; Z7 r5 ^& a1 n6 E# B
36.     }
    
37. }
    
38. 
    * P- H) Y0 \6 E3 Z& _6 I
39. - (NSMutableArray *)getIndexArray:(NSMutableArray *)array phone:(NSString *)phone {
    
40.     __block NSMutableArray *indexArray = [@[] mutableCopy];
    
41.     [results enumerateObjectsUsingBlock:^(NSString *_Nonnull obj, NSUInteger idx, BOOL *_Nonnull stop) {
    + o4 c: M& w; J0 h' L' q% c
42.         [indexArray appendObject:[self indexString:obj phone:phone]];
    ) `& C5 i. F5 r8 j  h  z
43.     }];
    
44.     return indexArray;
    / S1 N6 I8 O: Q
45. }
    * o5 w3 o' q  y" R- l2 J3 O
46. 
    
47. - (NSString *)indexString:(NSString *)s phone:(NSString *)phone {
    
48.     NSString *indexString = @"";
    0 g% w6 I0 v" V* i* E' \8 ^8 K
49.     NSMutableArray *sArray = [@[] mutableCopy];
    
50.     NSMutableArray *phoneArray = [@[] mutableCopy];
    - r7 K; U  m  T4 y" c0 i
51.     for (NSInteger i = 0; i < [s length]; i++) {
    
52.         [sArray addObject:[NSString stringWithFormat:@"%c", [s characterAtIndex:i]]];
    - w& v& S; A9 q8 k# `! C' ?6 d
53.     }
    
54.     for (NSInteger i = 0; i < [phone length]; i++) {
    0 {1 g8 G: e% I0 q  N2 |( V1 E. A
55.         [phoneArray addObject:[NSString stringWithFormat:@"%c", [phone characterAtIndex:i]]];
    
56.     }
    1 r4 ~+ z; x, [$ e8 `& y
57.     for (NSInteger i = 0; i < [phoneArray count]; i++) {
    : e8 t0 N: _( O
58.         NSUInteger index = [sArray indexOfObject:phoneArray[i]];
    
59.         indexString = [indexString stringByAppendingString:@(index).stringValue];
    
60.     }
    
61.     return indexString;
    4 L: Y( }7 `' I
62. }

复制代码

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

上述代码参考链接：
; k* ~  @% K2 e4 @0 U4 C: Dhttp://stackoverflow.com/questions/15738807/calculate-possible-permutations-of-an-array-of-numbers

感兴趣的还可以看一下下面的链接：
& L' W+ w3 r) Rhttp://stackoverflow.com/questions/15738807/calculate-possible-permutations-of-an-array-of-numbers
http://stackoverflow.com/questions/3791265/generating-permutations-of-nsarray-elements
0 b' Y% b$ ~  |( {) E) m0 _http://codereview.stackexchange.com/questions/57340/seeking-improved-objective-c-permutation-algorithm
, _" K! w( D* l9 ^. Vhttp://stackoverflow.com/questions/6617253/permutations-anagrams-in-objective-c-i-am-missing-something

9 a% W+ V  K& G/ T4 Y