4

私は、9つの文字を入力すると、それらの9文字のアナグラムを出力するiosアプリケーションを作成しています。対象となる単語、または論文の 9 文字の単語のようなものです。このリンクのように:

http://nineletterword.tompaton.com/

9 文字のアナグラムを提供するだけでなく、4 文字、5 文字、6 文字のアナグラムを提供します。すべての文字には、少なくとも中間文字が含まれています。

オフラインアプリにしたいので、Webサイトを参照したり、オンラインjsonを使いたくない...

ダウンロードした英語の辞書にある単語に 9 文字の配列を並べ替えることができるかどうかを確認するにはどうすればよいでしょうか。

たとえば、(a、b、a、n、D、o、n、e、d) の入力があります。「English Dictionary」と呼ばれる配列内の英単語である 4 文字以上の出力を取得するにはどうすればよいでしょうか。 「放棄」、「絆」、「死んだ」など、真ん中の文字「D」が含まれている必要があります...

最良の方法は、たくさんのループと if ステートメントですか、それとも xcode/objective c に何かがあり、4 文字のリストを取得して、可能なすべての配置を行うために使用できます...

乾杯

4

2 に答える 2

3

配列の検索ではなく、ルックアップに依存する別のアルゴリズムを提案させてください。

設定：

辞書内の単語を反復処理します。単語ごとに、同じ文字をアルファベット順に並べた文字列を作成します。この文字列をキーとして、元の単語の配列の辞書を作成します。

使用法：

これで、任意の文字の組み合わせのチェックを非常に迅速に行うことができます。上記のように文字を並べ替えて、結果のキーをマップで調べるだけです。

例：

元の配列:( bond, Mary, army )

アナグラム ルックアップ マップ:

{
   bdno : ( bond ),
   amry : ( Mary, army ),
}

このマップを使用すると、単語のアナグラムをすばやく確認できます。ディクショナリ配列の反復は必要ありません。

編集：

私が提案したアルゴリズムは、次の 3 つの部分に分かれています。

  1. オブジェクトのディクショナリからルックアップ マップを作成するセットアップ メソッド:anagramMap
  2. 文字ごとにソートされたキーを計算する方法:anagramKey
  3. 9 文字の単語に含まれる文字のすべての順列を検索し、マップ内の単語を検索するアルゴリズム: findAnagrams.

上のカテゴリとして 3 つのメソッドすべてを実装したものを次に示します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次を使用して可能な値をログに記録します。

for (NSString *anagram in [nineletters findAnagrams])
    NSLog(@"%@", anagram);
于 2013-04-08T10:12:06.450 に答える