Generowanie permutacji elementów NSArray

Question

Powiedzmy mam NSArray od NSNumbers tak: 1, 2, 3

to zbiór wszystkich możliwych permutacji będzie wyglądać mniej więcej tak:

1, 2 3

1, 3, 2

2, 1, 3

2, 3, 1

3, 1, 2

3, 2, 1

Co to dobry sposób, aby zrobić to w Objective-C?

Answer 1

Nie może być lepszy sposób to zrobić (w miejscu, czy coś), ale to wydaje się działać:

Header:

@interface NSArray (PermutationAdditions) 

- (NSArray *)allPermutations; 

@end 

implementacja:

@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 

Aby z niego skorzystać, po prostu #import plik nagłówkowy i wywołanie [yourArray allPermutations]; metoda zwróci tablicę zawierającą tablice dla każdej permutacji.

[Kod zaadaptowany z kodu PHP here.]

Answer 2

Użyłem kod z odpowiedzią Wevah za powyżej odkrył pewne problemy z nim więc o moich zmian, aby to działało poprawnie:

NSArray + permutacja .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

Możesz zmienić NSString *characters do id something i użyć go do każdego rodzaju obiektu

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

Expanded odpowiedź SSJ do

-log wydruków dla jasności

-work z dowolnego obiektu

-Więcej wyjaśnienia

-wyświetlić przypadki brzegowe, w których błąd może wyniknąć:

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

wyjście dziennika dla wejścia @ [@ 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

Niedawno natknął się na ten sam problem, i napisał rekurencyjną rozwiązanie, które moim zdaniem jest bardziej czytelny.Opiera się na głównej zasadzie, którą odnotowano pod numerem here. Ja tu jestem to w tym przypadku będzie to komuś pomóc:

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

wezwanie Próbka:

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

Wynik:

1, 2, 3

1, 3 , 2

2, 1, 3

2, 3, 1

3, 1, 2

3, 2, 1