permutazioni/Anagrammi in Objective-C - mi manca qualcosa

Question

(codice qui sotto per quanto riguarda la mia domanda)

Per this stack overflow question ho usato l'approccio di Pegolon a generare tutte le possibili permutazioni di un gruppo di personaggi all'interno di un NSString. Tuttavia, sto cercando di farlo non solo per generare un ANAGRAM che è tutte le permutazioni della stessa lunghezza, ma tutte le combinazioni possibili (qualsiasi lunghezza) dei caratteri in una stringa.

Qualcuno saprebbe come modificherei il seguente codice per farlo? Questo è molto simile a: Generate All Permutations of All Lengths - ma (per paura di dover rispondere ai compiti) non hanno lasciato il codice. Ho un esempio di ciò che pensavo lo avrebbe fatto in fondo a questo post ... ma non è così.

Quindi, il codice, come è, genera the, teh, hte, het, eth e eht quando somministrato THE. cosa ho bisogno è lungo le linee di: t, h, e, th, ht, te, he (ecc) in aggiunta a quanto sopra 3 combinazioni di caratteri.

Come cambierei questo, per favore. (ps: Ci sono due metodi in questo. Ho aggiunto allPermutationsArrayofStrings per ottenere i risultati come stringhe, come li voglio io, non solo una serie di caratteri in un altro array). Presumo che la magia si verifichi comunque in pc_next_permutation, ma ho pensato di parlarne.

In NSArray + Permutation.h

#import <Foundation/Foundation.h> 

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

@end 

in 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 

Il mio codice che ho pensato che sarebbe risolvere il problema:

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

lo so non sarebbe il più efficiente ... ma stavo cercando di testare.

Questo è quello che ho ottenuto:

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 

Come si può vedere, non una o due parole lettera - sto tirando fuori i miei capelli! (e non ho molto da vendere!)

Answer 1

Una cosa facile da fare sarebbe prendere tutti i sottoinsiemi di dimensioni k e utilizzare il codice che devi generare tutte le permutazioni del sottoinsieme. Questo è facile, ma non il più efficiente.

---

Ecco un approccio migliore. Si sta generando permutazioni lexicographically nella prima routine:

1234 
1243 
1324 
1342 
1423 
... 

Ogni volta che si chiama NSInteger *pc_next_permutation(NSInteger *perm, const NSInteger size), si ottiene il prossimo permutazione in ordine lex trovando la posizione corretta per cambiare. Quando lo fate, troncare dal dischetto è stato modificato per ottenere la seguente:

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

Spero che l'idea è chiara. Ecco un modo per implementarlo (in pseudocodice Objective C-like).

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

Ciò restituirà un array con le permutazioni parziali come descritto sopra. L'input per nextPerms deve essere lastObject dell'uscita di nextPerms.

Answer 2

Okay,

basso e sporco, per ora, tuttavia, questo è quello che ho fatto ...

ho cambiato il NSArray+Permutations.m essere il seguente:

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

I maggiori cambiamenti sono stati l'idea @PengOne aveva ... Restituire la stringa lessicale modificata risultante, ma anche accorciarla di 1 carattere alla volta e aggiungerla all'array restituito se non esisteva già.

Ho scelto di essere "economico" e di tenere traccia utilizzando NSMutableDictionary. Quindi se la stringa lessicalmente modificata non è stata elencata nel dizionario, è stata aggiunta.

È più o meno quello che pensavi di dover fare, @PengOne?

WAY più veloce di aggiungerli tutti e gestire i duplicati risultanti in seguito - e penso che funzioni come se ne avessi bisogno.