permutaciones/Anagramas en Objective-C - me falta algo (por debajo de código con respecto a mi pregunta)

Question

por this stack overflow question he utilizado el enfoque de Pegolon a generar todas las posibles permutaciones de un grupo de caracteres dentro de un NSString. Sin embargo, ahora estoy intentando que no solo genere una ANAGRAMA, que son todas las permutaciones de la misma longitud, sino todas las combinaciones posibles (cualquier longitud) de los caracteres en una cadena.

¿Alguien sabría cómo alteraría el siguiente código para que haga esto? Esto es muy parecido a: Generate All Permutations of All Lengths - pero (por miedo a que necesiten respuesta a la tarea) no dejaron el código. Tengo una muestra de lo que pensé que lo haría al final de esta publicación ... pero no fue así.

Por lo tanto, el código, tal cual, genera the, teh, hte, het, eth y eht cuando se administra THE. Lo que necesito es a lo largo de las líneas de: t, h, e, th, ht, te, he (etc) además de las 3 combinaciones de caracteres anteriores.

Cómo cambiar esto, por favor. (ps: Hay dos métodos en esto. Agregué allPermutationsArrayofStrings para obtener los resultados como cadenas, como los quiero, no solo como una matriz de caracteres en otra matriz). Supongo que la magia sucedería en pc_next_permutation de todos modos, pero pensé que lo mencionaría.

En NSArray + Permutation.h

#import <Foundation/Foundation.h> 

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

@end 

en 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 

Mi código que pensé que solucionar este 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]; 
       } 

Sé que no sería el más eficiente ... pero estaba tratando de probar.

Esto es lo que tengo:

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 

Como se puede ver, hay una o dos letras de palabras - Estoy tirando de mi pelo! (¡y no tengo mucho de sobra!)

Answer 1

Una cosa fácil de hacer sería tomar todos los subconjuntos de tamaño k y usar el código que tiene para generar todas las permutaciones del subconjunto. Esto es fácil, pero no el más eficiente.

---

Aquí hay un mejor enfoque. Estás generando permutaciones lexicográfico en la primera rutina:

1234 
1243 
1324 
1342 
1423 
... 

Cada vez que llame NSInteger *pc_next_permutation(NSInteger *perm, const NSInteger size), se obtiene la siguiente permutación con el fin lex al encontrar la posición correcta para cambiar. Cuando se hace esto, truncar desde el punto ha cambiado para obtener lo siguiente:

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

espero que la idea es clara. Aquí hay una forma de implementar esto (en pseudocódigo de Objective 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]; 
} 

Esto devolverá una matriz con las permutaciones parciales como se describe arriba. La entrada para nextPerms debe ser lastObject de la salida nextPerms.

Answer 2

bien,

abajo y sucio, por ahora, sin embargo, esto es lo que hice ...

he cambiado el NSArray+Permutations.m ser de la siguiente manera:

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

Los principales cambios fueron la idea @PengOne tenía ... Devuelve la cadena resultante modificada léxicamente pero también la acorta en 1 carácter a la vez y la agrega a la matriz devuelta si no existía ya.

Elegí ser "barato" al respecto y realizar un seguimiento con un NSMutableDictionary. Por lo tanto, si la cadena modificada léxicamente no figuraba en el diccionario, se agregó.

¿Es eso más o menos lo que pensaste que debería hacer, @PengOne?

MUCHO más rápido que agregarlos todos y tratar con los duplicados resultantes más tarde, y creo que funciona como lo necesito.