Üretme permütasyon

Question

en böyle NSNumbers bir NSArray var diyelim

1, 2 , 3

1, 3, 2

2, 1, 3

2, 3, 1

012.

3, 1, 2

3, 2,

amaç-c bunu yapmanın iyi bir yolu nedir 1?

Answer 1

bu (yerinde, ya da bir şey) yapmak için daha iyi bir yolu olabilir, ama bu iş gibi görünüyor:

Başlık:

@interface NSArray (PermutationAdditions) 

- (NSArray *)allPermutations; 

@end 

uygulaması:

@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 

Bunu kullanmak için, sadece #import başlık dosyasını ve [yourArray allPermutations] numaralı telefonu arayın; Yöntem, her bir permütasyon için dizileri içeren bir dizi döndürecektir.

Answer 2

Yukarıda Wevah cevabı kodu kullandık [. Kod PHP kodundan here uyarlanan] ve düzgün çalışması için taşıması için işte benim değişikliklerle bazı sorunlar keşfetti:

NSArray + Permütasyon .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

Sen id something için NSString *characters değiştirebilir ve nesne her türlü için kullanabilirsiniz

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 herhangi bir nesne

-daha ile netlik

-çalışma için

-log baskılar için ssj cevabı açıklamalar

hataların ortaya çıkabileceği kenar durumları

[3 ', 2', 1 ',] giriş @ için

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

günlük çıkış

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

Son zamanlarda aynı sorun tökezledi ve daha okunabilir inanıyoruz özyinelemeli çözelti yazdım.Bu, here no'lu ana prensibe dayanır.

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

Numune çağrı:

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

Sonuç:

1, 2, 3

1, 3 Ben birine yardım edecek durumda buradan da dahil ediyorum 2, 1, 3

,

2, 3, 1

3, 1, 2

3, 2,