来自字母的单词

Question

我在iOS中工作，而且我面临着一个问题。我有6个字母，我想查找可以由这6个字母生成的所有字符串。字符串的序列和长度在这里并不重要，字符串的含义也没有关系，因为我们可以用字典检查字符串以查找它是否是有效的单词。

那么有什么算法可以找到它？

例如：

输入6个字母是：NTLPAE

预计产出将是：

plan 
net 
planet 
lan 
tea 
lap 
.. 
.. 

这里输出的话仅仅是有效的话，但输出应该包含所有可能的单词，甚至无效的单词。

Answer 1

我得到了解决， 我想是以下。

-(NSArray*)totalWords:(NSArray*)letters 
{ 
    NSMutableArray *output=[[NSMutableArray alloc]init]; 

    for (int i=0; i<letters.count; i++) 
    { 
     for (int j=0; j<letters.count; j++) 
     { 
      if (i==j) continue; 
     for (int k=0; k<letters.count; k++) 
     { 
      NSString *str=[NSString stringWithFormat:@"%@%@%@",letters[i],letters[j],letters[k]]; 
      if(i!=j && j!=k && i!=k &&[self checkmeaning:str]) 
       [output addObject:str]; 
      for (int l=0; l<letters.count; l++) 
      { 
       NSString *str=[NSString stringWithFormat:@"%@%@%@%@",letters[i],letters[j],letters[k],letters[l]]; 
       if(i!=j && j!=k && i!=k && l!=i && l!=j && l!=k &&[self checkmeaning:str]) 
        [output addObject:str]; 
       for (int m=0; m<letters.count; m++) 
       { 
        NSString *str=[NSString stringWithFormat:@"%@%@%@%@%@",letters[i],letters[j],letters[k],letters[l],letters[m]]; 
        if(i!=j && j!=k && i!=k && l!=i && l!=j && l!=k && m!=i && m!=j && m!=k && m!=l &&[self checkmeaning:str]) 
         [output addObject:str]; 
        for (int n=0; n<letters.count; n++) 
        { 
         NSString *str=[NSString stringWithFormat:@"%@%@%@%@%@%@",letters[i],letters[j],letters[k],letters[l],letters[m],letters[n]]; 
         if(i!=j && j!=k && i!=k && l!=i && l!=j && l!=k && m!=i && m!=j && m!=k && n!=i && n!=j && n!=k &&n!=m &&n!=l && m!=l&&[self checkmeaning:str]) 
         [output addObject:str]; 
        } 
       } 
      } 
     } 
     } 
    } 

    NSLog(@"count :%i",[output count]); 
    NSLog(@"output array :\n%@",output); 
    return output; 
} 

Answer 2

这也许应该解决这个问题：

+ (void) logPermutations:(NSArray*)objects 
{ 
    if (objects == nil || [objects count] == 0) { 
     return; 
    } 
    NSMutableArray* copy = [objects mutableCopy]; 
    [self logPermutations:copy logedSoFar:@""]; 
} 

+ (void) logPermutations:(NSMutableArray*)objects 
       logedSoFar:(NSString*)log 
{ 
    if (objects == nil || [objects count] == 0) { 
     return; 
    } 
    NSUInteger count = [objects count]; 
    for (NSUInteger i = 0; i < count; ++i) { 
     id removed = [objects objectAtIndex:i]; 
     [objects removeObjectAtIndex:i]; 
     NSString* newlog = [NSString stringWithFormat:@"%@%@",log,[removed description]]; 
     NSLog(@"%@",newlog); 
     [self logPermutations:objects logedSoFar:newlog]; 
     [objects insertObject:removed atIndex:i]; 
    } 
} 

Answer 3

-(NSMutableArray*)genValidWords:(NSString*)tiles 
{ 
    /*===============EMPTY PREVIOUS ARRAY=================*/ 
    FINAL_VALID_WORDS=[[NSMutableArray alloc] init]; 
    posWords=[[NSMutableArray alloc] init]; 
    genWords=[[NSArray alloc] init]; 
    /*============EMPTY PREVIOUS ARRAY FINISH=============*/ 

    /*===============POSSIABLE NO OF WORDS FROM GIVEN LETTERS=================*/ 

    int length=[tiles length]; 
    int total=0; 
    for(long i=2;i<[tiles length]+1;i++) 
     total=total+([self factorialX:length]/[self factorialX:length-i]); 
    NSLog(@"POSSIABLE NO OF WORDS FROM LETTERS \"%@\" IS %d",tiles,total); 

    /*===============POSSIABLE NO OF WORDS FROM GIVEN LETTERS FINISH=================*/ 



    /*===============GET ARRAY OF ALL POSSIABLE WORDS FROM GIVEN LETTERS=============*/ 
    for(int i=2;i<[tiles length]+1;i++) 
    { 
     genWords=getPermutations(tiles, i); 
     [posWords addObjectsFromArray:genWords]; 
    } 
    NSLog(@"%@",posWords); 
    return posWords; 
} 
static NSMutableArray *results; 
void doPermute(NSMutableArray *input, NSMutableArray *output, NSMutableArray *used, int size, int level) 
{ 
    if (size == level) 
    { 
     NSString *word = [output componentsJoinedByString:@""]; 
     //if(check(word)) 
     [results addObject:word]; 
     return; 
    } 
    level++; 
    for (int i = 0; i < input.count; i++) 
    { 
     if ([used[i] boolValue]) 
     { 
      continue; 
     } 
     used[i] = [NSNumber numberWithBool:YES]; 
     [output addObject:input[i]]; 
     doPermute(input, output, used, size, level); 
     used[i] = [NSNumber numberWithBool:NO]; 
     [output removeLastObject]; 
    } 
} 
NSArray *getPermutations(NSString *input, int size) 
{ 
    results = [[NSMutableArray alloc] init]; 

    NSMutableArray *chars = [[NSMutableArray alloc] init]; 


    for (int i = 0; i < [input length]; i++) 
    { 
     NSString *ichar = [NSString stringWithFormat:@"%c", [input characterAtIndex:i]]; 
     [chars addObject:ichar]; 
    } 

    NSMutableArray *output = [[NSMutableArray alloc] init]; 
    NSMutableArray *used = [[NSMutableArray alloc] init]; 

    for (int i = 0; i < chars.count; i++) 
    { 
     [used addObject:[NSNumber numberWithBool:NO]]; 
    } 

    doPermute(chars, output, used, size, 0); 

    return results; 
} 
-(double) factorialX: (int) num { 
    double tempResult = 1; 
    for (int i=2; i<=num; i++) { 
     tempResult *= i; 
    } 
    return tempResult; 
} 
/*=======================Call Like this==================== 
NSmutableArray=getPermutations("Pass your string", pass your lenght); 
NsmutableArray=getPermutations("Janak", 2); 
NSMutableArray=[self genValidWords:@"Hello"]; 
will return all possiable combination of two letters 
=======================xxxxxxxxxx====================*/