Javaで文字を組み合わせて単語を形成するにはどうすればいいですか？

Question

私は長さnのさまざまな単語が必要で、各位置/インデックスにはm個の異なる要素があります。

例について

N =許容第一の位置要素のための5

である：H、Y、U、B、N

許容第二の位置の要素がある場合：E、S、D

許容第三の位置要素のため

は：L、O、P

許容第4の位置の要素がある場合：第五の位置要素アロについてL、O、P

結婚している：O、K、L

だから形成することができる様々な言葉がある：こんにちは、YELLK、BDPOKなど

の種類にすべての可能な単語を見つけるための効率的な方法かもしれない何Javaで効率的な方法？

Answer 1

私は各文字列を再帰的に選択し、次の文字列に移動するのが最も簡単な方法だと思います。私はJavaコードを実装しました。

static String s[] = {"HYUBN", "ESD", "LOP", "LOP", "OKL"}; 
    static ArrayList<String> comb; // arraylist is going to hold results. 

    static void dfs(String x,int i) { 
     if(i == s.length) { // there is no more string that can be generated 
      comb.add(x); // save the found string 
      return; 
     } 
     for(int j=0;j<s[i].length();j++) // for each character in the current string 
      dfs(x+s[i].charAt(j),i+1); // take the current character and move to the next string 
    } 

    public static void main(String[] args) { 
     comb = new ArrayList<>(); 
     dfs("",0); 
     for(String x:comb) out.print(x + " "); 
    } 

Answer 2

すべての可能な単語を見つける最も効率的な方法は、統計と確率のクラスを取り、組み合わせと並べ替えがどのように計算されるかを調べることです。提案された例には5 * 3 * 3 * 3 * 3の組み合わせがあります。

はい、Javaは問題のすべての組み合わせを生成する効果的な方法ですが、他の言語も同様に動作します。あなたは紙と鉛筆でそれを行うこともできますが、あなたは対処しなければならない組み合わせの数に応じてコンピュータを望むかもしれません。

幸運にも、コミュニティはあなたが思いつくサンプルコードを見ていきたいと思っています。

Answer 3

効率性は、可能な単語の辞書がどのように構成されているかに大きく依存します。アルファベット順（Java配列またはArrayList）で構成されている場合、有効な組み合わせが構築されている（左から右へ）かどうかを確認すると、多数のチェックが除外されます。例えば、A JavaのTreeMapのがさらに良くデータすることができ

...「... ND」をチェックし、それから始まる全く言葉がNDLLO、NDLLK、NDLLL、NDLOOをチェック ないことで時間を節約しません見つけます構造体はインクリメンタルサーチのために使用されますが、単語のソースが注文されている場合は単純な配列よりも構築に時間がかかり、メモリを増やす可能性があり、単純にすべての単語を含むファイルから配列に追加しています。

TreeMapとOrdersListのバイナリ検索は、それぞれO（log n）時間かかるので、最初の文字が可能な限り一致しなくなるとすぐに単語を除外することができます。 "NDA"のような略語を含む非常に徹底的な辞書は、より多くをチェックします。小さな辞書は、2文字の組み合わせにつき1つまたは2つの小切手しか必要としないことがあります（1つの文字が常に単語を開始するので、

初期設定時にO（n）ルックアップを行うために、単語セット（たとえば、Java HashMapを使用）のすべての単語の最初の数文字をハッシュすることができます。速度。 （HE、HEL、HELL、HELLO、YE、YEL、...大きなメモリコストです）すべてのインクリメンタルな可能性をハッシュした場合、インクリメンタルチェックはすべてO（n）になります。言葉を排除する。

より洗練：我々はワードセットの編成の制御を持っている場合、我々は素数のモジュロを使用して文字の異なる順序で単語を注文することができます：

"HELLO" rearranged by mod 7, for example would be: "HLOEL" 

これは、より良い性能を与えることができるので、共通の接頭語の周りに自然に発生するクラスタリングのいくつかを削除します。素数が高いほど、（フラットな）分布が良くなります。これを最初のn回のルックアップでハッシュと組み合わせると、O（n）とO（log n）の間でパフォーマンスが変化します。