问题描述
我在做一个iOS应用程序，你输入9 lettes以及9字母它将输出字谜。它像目标词，还是在纸9字母的单词。像此链接：
I'm Making a an ios application where you input 9 lettes and it will output anagrams of those 9 letters. It is like the target word, or 9 letter word in the paper. Like this link:
它不只是提供字谜为9个字母，它会做它的4个字母，5个字母，6个字母......所有这一切都至少包含字母中间。
It doesn't just provide anagrams for 9 letters, it will do it for 4 letters, 5 letters, 6 letters... all of which contain at least the middle letter.
我要使它成为离线应用程序，所以我不想引用任何网站或使用在线JSON ...
I want to make it an offline application, so I don't want to reference any websites or use an online json...
我怎么会去检查，如果9个字母组成的数组可以重新整理成一个字，是我已经下载了一本英语词典。
How would I go about checking if an array of the 9 letters can be rearranged into a word which is in an English dictionary which I have downloaded.
例如。我的输入（A，B，A，N， D ，O，N，E，D）：我将如何得到的4个字以上是英文单词数组中的输出所谓的汉英大辞典，必须包含中间的字母D - 像放弃，债券，死......
E.g. I have the input of (a,b,a,n,D,o,n,e,d): how would I get the output of 4 letters or more that are English words in an array called "English Dictionary" which must contains the middle letter "D" - like "abandon", "bond", "dead"...
是最佳的方法很多，很多循环和if语句或者是有什么在X code / Objective C的，我可以用它来只得到4个字母列表，然后有这一切成为可能的安排..
Is the best method lots and lots of loops and if statements or is there something in xcode/ objective c which I can use to just get the list of 4 letters and then have all possible arrangements of it...
干杯
推荐答案
让我提出一个不同的算法依赖于查找，而不是通过一个数组的搜索。
Let me propose a different algorithm that depends on a lookup, not a search through an array.
设置：
遍历字典中的单词。对于每一个字，创建具有相同的字符，按字母顺序排序的字符串。使用此字符串作为重点，创建的原话阵列的字典。
Iterate over the words in the dictionary. For each word, create a string with the same characters, sorted alphabetically. Using this string as a key, create a dictionary of arrays of the original words.
用法：
现在你可以做任何字符组合的检查非常快。就像上面的字符进行排序，并期待由此产生的关键起来的地图
Now You can do the check on any character combination very quickly: Just sort the characters like above and look the resulting key up in the map.
例如：
原始数组：（债券，玛丽，军队）
字谜查找图：
{
bdno : ( bond ),
amry : ( Mary, army ),
}
使用这种地图是非常快的检查任何单词的字谜。需要字典阵列上没有重复。
Using this map it's very fast to check anagrams of any word. No iteration over the dictionary array is needed.
编辑：
我的算法分裂分为三个部分：
My proposed algorithm splits in three parts:
- 系统设置方法来构建从对象的字典查找地图：
anagramMap - 来计算字符逐个字符的方法来分类的关键：
anagramKey - 的发现中包含九个字母的单词字符的所有排列并查找地图中的字的算法：
findAnagrams
- A setup method to build the lookup map from a dictionary of objects:
anagramMap - A method to calculate the character-by-character sorted key:
anagramKey - An algorithm that finds all permutations of the characters contained in the nine letter word and looks up the words in the map:
findAnagrams.
下面是三种方法作为一个类别对实施的NSString ：
Here's an implementation of all three methods as a category on NSString:
@interface NSString (NSStringAnagramAdditions)
- (NSSet *)findAnagrams;
@end
@implementation NSString (NSStringAnagramAdditions)
+ (NSDictionary *)anagramMap
{
static NSDictionary *anagramMap;
if (anagramMap != nil)
return anagramMap;
// this file is present on Mac OS and other unix variants
NSString *allWords = [NSString stringWithContentsOfFile:@"/usr/share/dict/words"
encoding:NSUTF8StringEncoding
error:NULL];
NSMutableDictionary *map = [NSMutableDictionary dictionary];
@autoreleasepool {
[allWords enumerateLinesUsingBlock:^(NSString *word, BOOL *stop) {
NSString *key = [word anagramKey];
if (key == nil)
return;
NSMutableArray *keyWords = [map objectForKey:key];
if (keyWords == nil) {
keyWords = [NSMutableArray array];
[map setObject:keyWords forKey:key];
}
[keyWords addObject:word];
}];
}
anagramMap = map;
return anagramMap;
}
- (NSString *)anagramKey
{
NSString *lowercaseWord = [self lowercaseString];
// make sure to take the length *after* lowercase. it might change!
NSUInteger length = [lowercaseWord length];
// in this case we're only interested in anagrams 4 - 9 characters long
if (length < 4 || length > 9)
return nil;
unichar sortedWord[length];
[lowercaseWord getCharacters:sortedWord range:(NSRange){0, length}];
qsort_b(sortedWord, length, sizeof(unichar), ^int(const void *aPtr, const void *bPtr) {
int a = *(const unichar *)aPtr;
int b = *(const unichar *)bPtr;
return b - a;
});
return [NSString stringWithCharacters:sortedWord length:length];
}
- (NSSet *)findAnagrams
{
unichar nineCharacters[9];
NSString *anagramKey = [self anagramKey];
// make sure this word is not too long/short.
if (anagramKey == nil)
return nil;
[anagramKey getCharacters:nineCharacters range:(NSRange){0, 9}];
NSUInteger middleCharPos = [anagramKey rangeOfString:[self substringWithRange:(NSRange){4, 1}]].location;
NSMutableSet *anagrams = [NSMutableSet set];
// 0x1ff means first 9 bits set: one for each character
for (NSUInteger i = 0; i <= 0x1ff; i += 1) {
// skip permutations that do not contain the middle letter
if ((i & (1 << middleCharPos)) == 0)
continue;
NSUInteger length = 0;
unichar permutation[9];
for (int bit = 0; bit <= 9; bit += 1) {
if (i & (1 << bit)) {
permutation[length] = nineCharacters[bit];
length += 1;
}
}
if (length < 4)
continue;
NSString *permutationString = [NSString stringWithCharacters:permutation length:length];
NSArray *matchingAnagrams = [[self class] anagramMap][permutationString];
for (NSString *word in matchingAnagrams)
[anagrams addObject:word];
}
return anagrams;
}
@end
假设在一个名为 nineletters 变量，你会使用日志的可能值的测试字符串：
Assuming a test string in a variable called nineletters you would log the possible values using:
for (NSString *anagram in [nineletters findAnagrams])
NSLog(@"%@", anagram);
这篇关于从Array重新整理信件和检查安排在阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！