hoán vị Tạo các yếu tố NSArray

Question

Hãy nói rằng tôi có một NSArray của NSNumbers như thế này: 1, 2, 3

Sau đó tập hợp tất cả các hoán vị có thể sẽ giống như thế này:

1, 2 , 3

1, 3, 2

2, 1, 3

2, 3, 1

012.

3, 1, 2

3, 2, 1

một cách tốt để làm điều này trong Objective-C là gì?

Answer 1

Có thể có một cách tốt hơn để làm điều này (tại chỗ, hoặc một cái gì đó), nhưng điều này dường như làm việc:

Tiêu đề:

@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 

Để sử dụng nó, chỉ cần #import tệp tiêu đề và gọi [yourArray allPermutations]; phương thức này sẽ trả về một mảng chứa các mảng cho mỗi hoán vị.

[Mã chuyển thể từ mã PHP here.]

Answer 2

Tôi đã sử dụng mã từ câu trả lời Wevah của trên và phát hiện ra một số vấn đề với nó như vậy ở đây thay đổi của tôi để làm cho nó hoạt động đúng:

NSArray + hoán vị .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 3

Bạn có thể thay đổi NSString *characters-id something và sử dụng nó cho bất kỳ loại đối tượng

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 copy] autorelease]; 
     [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

mở rộng câu trả lời SSJ để

in -log cho rõ ràng

-Làm với bất kỳ đối tượng

-Xem thêm giải thích

trường hợp cạnh phát hiện có lỗi có thể dẫn đến

[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); 
} 

dữ liệu ghi nhận cho đầu vào @ [@ 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 

Answer 5

Gần đây tôi stumbled khi cùng một vấn đề, và đã viết một giải pháp đệ quy mà tôi tin là dễ đọc hơn.Nó dựa trên nguyên tắc cốt lõi được ghi nhận here. Tôi đưa nó vào xem trong trường hợp nó sẽ giúp ai đó:

- (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]]; 
} 

gọi mẫu:

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

Kết quả:

1, 2, 3

1, 3 , 2

2, 1, 3

2, 3, 1

3, 1, 2

3, 2, 1