8

指定された文字列の可能なすべての文字の組み合わせを 2 文字まで生成するアルゴリズム

ここにあるような、AS3 でアナグラム ソルバーを作成しようとしています。

http://homepage.ntlworld.com/adam.bozon/anagramsolver.htm

さまざまな長さの文字列に対して考えられるすべての文字の組み合わせを生成することに頭を悩ませています。固定長の順列のみを生成していた場合、私にとってはそれほど問題にはなりません...しかし、文字列の長さを減らして、元の文字セットから可能なすべての順列を取得しようとしています元の文字列よりも小さい最大長の文字列。たとえば、文字列の長さを 2 にしたいが、「abc」という 3 文字の文字列がある場合、出力は ab ac ba bc ca cb となります。

理想的には、アルゴリズムは、元の文字列の長さから最小の文字列の長さ 2 までの可能な組み合わせの完全なリストを生成します。おそらく、これを行うための小さな再帰アルゴリズムがあると感じていますが、私の頭脳を包み込むことはできません。それ。私はAS3で働いています。

ありがとう！

4

5 に答える 5

8

リンクした種類のアナグラム ソルバーを作成する目的で、要求しているアルゴリズムは必要ありません。また、非常に高価です。

MONKEYたとえば、 のような 6 文字の単語を見てみましょう。単語の 6 文字すべてが異なるため、次のように作成します。

  • 6*5*4*3*2*1 異なる 6 文字の単語
  • 6*5*4*3*2 の異なる 5 文字の単語
  • 6*5*4*3 の異なる 4 文字の単語
  • 6*5*4 の異なる 3 文字の単語
  • 6*5 の異なる 2 文字の単語
  • 合計1950ワード

おそらく、あなたは 1950 語すべて (例えば 'OEYKMN') をアナグラムとして吐き出そうとしているわけではありません (それらはそうですが、それらのほとんどは意味不明でもあります)。あなたは合法的な英語の単語の辞書を持っていると思います。これらの単語のいずれかがクエリ単語のアナグラムであるかどうかを確認したいだけで、すべての文字を使用しないというオプションがあります。

その場合、問題は単純です。

2 つの単語が互いにアナグラムであるかどうかを判断するには、それぞれの文字が何回使われているかを数え、これらの数字を比較するだけです。

大文字と小文字を区別せずに、26 文字の AZ のみに制限しましょう。必要なcountLettersことは、単語を受け取り、26 個の数値の配列を返す関数を作成することです。配列の最初の数値はA単語内の文字の数に対応し、2 番目の数値は の数に対応しますB。

次に、2 つの単語W1andは、 for every !のW2場合、正確なアナグラムです。つまり、各単語は各文字をまったく同じ回数使用しています。countLetters(W1)[i] == countLetters(W2)[i]i

MONEYサブアナグラム (は のサブアナグラムMONKEY)と呼ぶものは、 if for every !W1のサブアナグラムです。つまり、サブアナグラムは特定の文字を使用することはできますが、使用する文字を増やすことはできません!W2countLetters(W1)[i] <= countLetters(W2)[i]i

(注:MONKEYは のサブアナグラムでもありMONKEYます)。

これにより、十分に高速なアルゴリズムが得られます。クエリ文字列が与えられた場合、辞書を 1 回読み込んで、各単語の文字カウント配列をクエリ単語の文字カウント配列と比較するだけです。いくつかの小さな最適化を行うことができますが、これで十分です。

または、最高のパフォーマンスが必要な場合は、辞書 (事前にわかっている) を前処理して、サブアナグラム関係の有向非巡回グラフを作成できます。

説明のために、このようなグラフの一部を次に示します。

 D=1,G=1,O=1  ----------> D=1,O=1
  {dog,god}   \            {do,od}
               \
                \-------> G=1,O=1
                           {go}

基本的に、各ノードは、同じ文字カウント配列を持つすべての単語のバケットです (つまり、それらは正確なアナグラムです)。次に、ノード fromN1からN2ifN2の配列が<=(上で定義されているように)N1の配列です (推移的な削減を実行して、最小量のエッジを保存できます)。

次に、単語のすべてのサブアナグラムを一覧表示するには、その文字カウント配列に対応するノードを見つけ、そのノードから到達可能なすべてのノードを再帰的に探索するだけです。すべてのバケットにサブアナグラムが含まれます。

于 2010-03-13T21:20:04.863 に答える
3

次のjsコードは、n文字の単語で可能なすべての「単語」を検索します。もちろん、これはそれらが本当の言葉であるという意味ではありませんが、あなたにすべての組み合わせを与えます。私のマシンでは、7文字の単語で約0.4秒、9文字の単語で15秒かかります（繰り返し文字がない場合は、最大でほぼ100万の可能性があります）。しかし、それらの時代には、辞書を調べて、どれが本当の言葉であるかを見つけることが含まれます。

var getWordsNew=function(masterword){
var result={}
 var a,i,l;
function nextLetter(a,l,key,used){
     var i;
    var j;
    if(key.length==l){
        return;
    }
    for(i=0;i<l;i++){
        if(used.indexOf(""+i)<0){
            result[key+a[i]]="";
            nextLetter(a,l,key+a[i],used+i);
        }
    }
 }
a=masterword.split("");
  l=a.length;
for (i = 0; i < a.length; i++) {
    result[a[i]] = "";
    nextLetter(a, l, a[i], "" + i)
}
return result;
}

で完全なコード

単語の中の単語を見つけるためのコード

于 2012-12-05T06:22:10.077 に答える
0

文字の完全なグラフですべてのパスを見つけることにより、アルファベットのすべての単語を生成できます。各文字から深さ優先検索を実行し、各ポイントで現在のパスを返すことにより、そのグラフ内のすべてのパスを見つけることができます。

于 2010-03-13T20:41:47.250 に答える
0

nが語彙のサイズである単純なO（N）があります。各単語の文字を語彙またはそれ以上に並べ替え、それらのバイナリ マスクを作成し、持っている文字を比較するだけです。

于 2010-03-14T12:16:50.610 に答える
0

ある種の手配が必要です。順列アルゴリズムに精通している場合は、十分な数値が生成されたことを確認するためのチェックがあることを知っています。その制限を変更するだけです：

AS3 はわかりませんが、擬似コードは次のとおりです。

st = an array
Arrangements(LettersInYourWord, MinimumLettersInArrangement, k = 1)
  if ( k > MinimumLettersInArrangements )
  {
    print st;
  }

  if ( k > LettersInYourWord )
    return;      

  for ( each position i in your word that hasn't been used before )
    st[k] = YourWord[i];
    Arrangements(<same>, <same>, k + 1);

"abc" および Arrangements(3, 2, 1) の場合。これは印刷されます：

ab
abc
ac
acb
...

最初に 3 つ、次に 2 つが必要な場合は、次のことを考慮してください。

st = an array
Arrangements(LettersInYourWord, DesiredLettersInArrangement, k = 1)
  if ( k > DesiredLettersInArrangements )
  {
    print st;
    return
  }

  for ( each position i in your word that hasn't been used before )
    st[k] = YourWord[i];
    Arrangements(<same>, <same>, k + 1);

次に、「abc」呼び出しArrangements(3, 3, 1);の場合Arrangements(3, 2, 1);

于 2010-03-13T18:22:28.443 に答える