hoán vị/Tham khảo trong Objective-C - tôi thiếu cái gì

Question

(mã dưới đây liên quan đến câu hỏi của tôi)

mỗi this stack overflow question tôi đã sử dụng cách tiếp cận Pegolon để tạo ra tất cả các hoán vị có thể của một nhóm các nhân vật bên trong một NSString. Tuy nhiên, bây giờ tôi đang cố gắng làm cho nó không chỉ tạo ra một ANAGRAM mà là tất cả hoán vị có cùng độ dài, nhưng tất cả các kết hợp có thể (bất kỳ độ dài nào) của các ký tự trong một chuỗi.

Có ai biết làm thế nào tôi sẽ thay đổi mã sau đây để làm cho nó để làm điều này? Điều này giống như: Generate All Permutations of All Lengths - nhưng (vì sợ họ cần câu trả lời cho bài tập về nhà) họ không để lại mã. Tôi có một mẫu của những gì tôi nghĩ sẽ làm điều đó ở dưới cùng của bài đăng này ... nhưng nó không.

Vì vậy, mã này, như là, tạo ra the, teh, hte, het, eth và eht khi trao THE. Những gì tôi cần là dọc theo các dòng: t, h, e, th, ht, te, he (v.v) ngoài các kết hợp 3 ký tự ở trên.

Làm cách nào để thay đổi điều này, vui lòng. (ps: Có hai phương pháp trong điều này. Tôi đã thêm allPermutationsArrayofStrings để nhận kết quả trở lại dưới dạng chuỗi, như tôi muốn chúng, không chỉ là một mảng các ký tự trong mảng khác). Tôi giả sử sự kỳ diệu sẽ xảy ra trong pc_next_permutation anyway - nhưng nghĩ rằng tôi sẽ đề cập đến nó.

Trong NSArray + Permutation.h

#import <Foundation/Foundation.h> 

@interface NSArray(Permutation) 
- (NSArray *)allPermutationsArrayofArrays; 
- (NSArray *)allPermutationsArrayofStrings; 

@end 

trong NSArray + Permutation.m:

#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 *)allPermutationsArrayofArrays 
{ 
    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; 
} 

- (NSArray *)allPermutationsArrayofStrings 
{ 
    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 { 
     NSMutableString *newPerm = [[[NSMutableString alloc]initWithString:@"" ]autorelease]; 

     for (NSInteger i = 0; i <= size; ++i) 
     { 
      [newPerm appendString:[self objectAtIndex:perm[i]]]; 
     } 
     [perms addObject:newPerm]; 
    } while ((perm = pc_next_permutation(perm, size)) && ++permutationCount < MAX_PERMUTATION_COUNT); 
    free(perm); 

    return perms; 
} 

@end 

Mã của tôi mà tôi nghĩ sẽ sửa lỗi này:

for (NSInteger i = 1; i <= theCount; i++) { 
       NSRange theRange2; 
       theRange2.location = 0; 
       theRange2.length = i; 
       NSLog(@"Location: %i (len: %i) is: '%@'",theRange2.location,theRange2.length,[array subarrayWithRange:theRange2]); 

       NSArray *allWordsForThisLength = [[array subarrayWithRange:theRange2] allPermutationsArrayofStrings]; 
       for (NSMutableString *theString in allWordsForThisLength) 
       { 
        NSLog(@"Adding %@ as a possible word",theString); 
        [allWords addObject:theString]; 
       } 

Tôi biết nó sẽ không hiệu quả nhất .. nhưng tôi đã cố thử nghiệm.

Đây là những gì tôi nhận:

2011-07-07 14:02:19.684 TA[63623:207] Total letters in word: 3 
2011-07-07 14:02:19.685 TA[63623:207] Location: 0 (len: 1) is: '(
    t 
)' 
2011-07-07 14:02:19.685 TA[63623:207] Adding t as a possible word 
2011-07-07 14:02:19.686 TA[63623:207] Location: 0 (len: 2) is: '(
    t, 
    h 
)' 
2011-07-07 14:02:19.686 TA[63623:207] Adding th as a possible word 
2011-07-07 14:02:19.687 TA[63623:207] Adding ht as a possible word 
2011-07-07 14:02:19.688 TA[63623:207] Location: 0 (len: 3) is: '(
    t, 
    h, 
    e 
)' 
2011-07-07 14:02:19.688 TA[63623:207] Adding the as a possible word 
2011-07-07 14:02:19.689 TA[63623:207] Adding teh as a possible word 
2011-07-07 14:02:19.690 TA[63623:207] Adding hte as a possible word 
2011-07-07 14:02:19.691 TA[63623:207] Adding het as a possible word 
2011-07-07 14:02:19.691 TA[63623:207] Adding eth as a possible word 
2011-07-07 14:02:19.692 TA[63623:207] Adding eht as a possible word 

Như bạn thấy, không có một hoặc hai lá thư từ - Tôi đang kéo tóc của tôi ra! (và tôi không có nhiều phụ tùng!)

Answer 1

Một điều dễ làm là lấy tất cả các tập hợp con có kích thước k và sử dụng mã bạn phải tạo tất cả hoán vị của tập hợp con. Điều này rất dễ, nhưng không hiệu quả nhất.

---

Đây là cách tiếp cận tốt hơn. Bạn đang tạo ra hoán vị thứ tự từ điển trong các thói quen đầu tiên:

1234 
1243 
1324 
1342 
1423 
... 

Mỗi lần bạn gọi NSInteger *pc_next_permutation(NSInteger *perm, const NSInteger size), bạn sẽ có được hoán vị tiếp theo nhằm lex bằng cách tìm đúng vị trí để thay đổi. Khi bạn làm điều đó, cắt ngắn từ vị trí bạn đã thay đổi để nhận được các thông tin sau:

1234 123 12 1 
1243 124 
1324 132 13 
1342 134 
1423 142 14 
1432 143 
2143 214 21 2 
... 

Tôi hy vọng ý tưởng này là rõ ràng. Dưới đây là một cách để thực hiện điều này (trong mã giả tạo giống như C).

-(NSMutableArray *)nextPerms:(Perm *)word { 
    int N = word.length; 
    for (int i=N-1; i > 0; ++i) { 
     if (word[i-1] < word[i]) { 
      break; 
     } else if (i==1) { 
      i = 0; 
     } 
    } 
    // At this point, i-1 is the leftmost position that will change 
    if (i == 0) { 
     return nil; 
    } 
    i = i-1; 
    // At this point, i is the leftmost position that will change 
    Perm *nextWord = word; 
    for (int j=1; j <= N-i; ++j) { 
     nextWord[i+j] = word[N-j]; 
    } 
    nextWord[i] = nextWord[i+1]; 
    nextWord[i+1] = word[i]; 

    // At this point, nextPerm is the next permutation in lexicographic order.  

    NSMutableArray *permList = [[NSMutableArray alloc] init]; 
    for (int j=i; j<N; ++j) { 
     [permList addObject:[nextWord subwordWithRange:NSMakeRange(0,i)]]; 
    } 
    return [permList autorelease]; 
} 

Điều này sẽ trả về một mảng với hoán vị một phần như được mô tả ở trên. Dữ liệu nhập cho nextPerms phải là lastObject của đầu ra là nextPerms.

Answer 2

Okay,

Down và bẩn cho bây giờ, tuy nhiên, đây là những gì tôi đã làm ...

Tôi đã thay đổi NSArray+Permutations.m để thực hiện như sau:

- (NSArray *)allPermutationsArrayofStrings 
{ 
    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]; 
    NSMutableDictionary *permsDict = [[NSMutableDictionary alloc] init]; 

    do { 
     NSMutableString *newPerm = [[[NSMutableString alloc]initWithString:@"" ]autorelease]; 

     for (NSInteger i = 0; i <= size; ++i) 
     { 
      [newPerm appendString:[self objectAtIndex:perm[i]]]; 
     } 

     if ([permsDict objectForKey:newPerm] == nil) 
     { 
      [permsDict setObject:@"1" forKey:newPerm]; 
      [perms addObject:newPerm]; 
     } 

     for (NSInteger i = 1; i <= [newPerm length]; ++i) 
     { 
      NSRange theRange; 
      theRange.location = 0; 
      theRange.length = i; 
      if ([permsDict objectForKey:[newPerm substringToIndex:i]] == nil) 
      { 
       [permsDict setObject:@"1" forKey:[newPerm substringToIndex:i]]; 
       [perms addObject:[newPerm substringToIndex:i]]; 
      } 
     } 

    } while ((perm = pc_next_permutation(perm, size)) && ++permutationCount < MAX_PERMUTATION_COUNT); 
    free(perm); 

    [permsDict release]; 

    return perms; 
} 

Những thay đổi chủ yếu là ý tưởng @PengOne đã ... Trả lại chuỗi kết quả đã được thay đổi từ từ, nhưng cũng rút ngắn chuỗi 1 ký tự tại một thời điểm và thêm nó vào mảng được trả về nếu nó không tồn tại.

Tôi chọn "rẻ tiền" và theo dõi bằng cách sử dụng NSMutableDictionary. Vì vậy, nếu chuỗi thay đổi từ vựng không được liệt kê trong từ điển, nó đã được thêm vào.

Điều đó có nghĩa là bạn nghĩ mình nên làm gì nhiều hơn, @PengOne?

CÁCH nhanh hơn việc thêm tất cả và xử lý các bản sao kết quả sau - và tôi nghĩ nó hoạt động như tôi cần.