1

25万語の辞書（txtファイル）があります。それらの単語のそれぞれについて、可能なすべてのアナグラムをスローするスクリプトを考え出します（各アナグラムも辞書に含まれている必要があります）。

理想的には、スクリプトは次の形式で出力されます。

word1：anagram1、anagram2 .. ..

word2：anagram1、anagram2 .. ..

どんな助けでも大歓迎です。

4

4 に答える 4

1

これに触発されて、 Trieを作成することをお勧めします。

次に、Nレベルのトライには、可能なすべてのアナグラムが含まれます（Nは元の単語の長さです）。さて、さまざまなサイズの単語を取得するには、単にトライをトラバースすることをお勧めします。3文字のサブワードすべてについて、トライの3レベルの深さのすべての文字列を作成します。

私はこれをテストしなかったので、これについてはよくわかりませんが、これは興味深い挑戦であり、この提案は私がどのようにそれに取り組み始めるかということになるでしょう。

それが少し役立つことを願っています=）

于 2012-10-11T00:01:19.997 に答える
1

アナグラムウィークに違いない。

以前の質問に提出した回答を紹介します：https ：//stackoverflow.com/a/12811405/128421 。一般的な文字を含む単語をすばやく検索するためのハッシュを作成する方法を示します。

あなたの目的のために、部分文字列/内部単語を見つけるために、あなたはまた可能な内部単語を見つけたいと思うでしょう。開始単語に基づいて、さまざまなサイズの文字の一意の組み合わせをすばやく見つける方法は次のとおりです。

word = 'misses'
word_letters = word.downcase.split('').sort
3.upto(word.length) { |i| puts word_letters.combination(i).map(&:join).uniq }

eim
eis
ems
ess
ims
iss
mss
sss
eims
eiss
emss
esss
imss
isss
msss
eimss
eisss
emsss
imsss
eimsss

これらの組み合わせができたら、それらを分割し（または実行しないでjoin）、前の回答で作成したハッシュでルックアップを実行します。

于 2012-10-10T23:57:14.180 に答える
0 
h = Hash.new{[]}
array_of_words.each{|w| h[w.downcase.chars.sort].push(w)}
h.values
于 2012-10-11T01:06:46.373 に答える
0

私がこれまでに試したことPerl：

use strict;
use warnings;

use Algorithm::Combinatorics qw(permutations);

die "First argument should be a dict\n" unless $ARGV[0] or die $!;
open my $fh, "<", $ARGV[0] or die $!;

my @arr = <$fh>;
my $h = {};

map { chomp; $h->{lc($_)} = [] } @arr;

foreach my $word (@arr) {
    $word = lc($word);
    my $chars = [ ( $word =~ m/./g ) ];
    my $it = permutations($chars);

    while ( my $p = $it->next ) {
        my $str = join "", @$p;

        if ($str ne $word && exists $h->{$str}) { 
            push @{ $h->{$word} }, $str
                unless grep { /^$str$/ } @{ $h->{$word} };
        }
    }

    if (@{ $h->{$word} }) {
        print "$word\n";
        print "\t$_\n" for @{ $h->{$word} };
    }
}

END{ close $fh; }

速度は改善される可能性がありますが、機能します。

パッケージからフランス語のdictを使用します。words archlinux

例

$ perl annagrammes.pl /usr/share/dict/french
abaissent
        absentais
        abstenais
abaisser
        baissera
        baserais
        rabaisse
(...)

注 perlモジュールをインストールするには：

cpan -i Algorithm::Combinatorics
于 2012-10-11T01:33:41.113 に答える