文字列の組み合わせを作成するJavaの再帰について

Question

質問は、与えられた長さnに対して "cc"と "ddd"で構成される文字列のすべての可能な組み合わせを含むセットを返すように求めていました。

たとえば、与えられた長さが5の場合、セットには "ccddd"と "dddcc"が含まれます。 及び長さ6「CCCCCC」を含む設定返す、
及び長さ7は12の異なる組み合わせなどに返されます「ccdddcc」、「dddcccc」、「ccccddd」 と長さ12をcontating設定返す「DDDDDD」

ただし、返されるセットは空です。 助けてもらえますか？

は、私はあなたのアプローチを再考する必要があると思う

public static Set<String> set = new HashSet<String>(); 

public static Set<String> generateset(int n) { 


    String s = strings(n,n,""); 


    return set; // change this 
} 

public static String strings(int n,int size, String s){ 


    if(n == 3){ 
     s = s + ("cc"); 
     return "";} 
    if(n == 2){ 
     s = s + ("ddd"); 
     return "";} 
    if(s.length() == size) 
     set.add(s); 

    return strings(n-3,size,s) + strings(n-2,size,s); 
} 

Answer 1

「extremeply貧弱なコーディングスタイルを理解してください」。これは簡単な問題ではないので、Javaを非常に慣れていない（他のプログラミング言語にあまり慣れていない）場合は、このようなことに取り組む前に、セット、リスト、またはその他のコレクションに関する簡単な問題を試してみてください。 。

とにかく試してみたいと思います。このような再帰的な問題では、どのようにタスクを達成するかについて非常に明確な考え方が必要です。私はあなたに一般的なアイデアがあると思うが、はるかに明確にする必要がある。ここで私が問題にアプローチする方法をです：

（1）あなたが欲しいあなたの再帰的な方法は、私の知る限り、単一Stringを返し、長さNの文字列のリスト（またはセット）を返すメソッド結果の文字列が何であるかを明確に定義する必要はありません。 （明確な定義はプログラミングでは非常に重要ですが、複雑な再帰的な問題を解決する場合はさらにそうです）

（2）文字列は"cc"または"ddd"で始まります。したがって、結果リストを作成するには、次のようにする必要があります。

（2a）長さN-2のすべての文字列を検索します。ここでは、その長さのすべての文字列を取得するために再帰呼び出しが必要です。そのリストのすべての文字列を調べ、各文字列の先頭に"cc"を追加します。

（2b）同様に、再帰呼び出しで長さN-3のすべての文字列を見つけます。そのリスト内のすべての文字列を調べ、"ddd"を前面に追加します。

（2c）結果のリストは、ステップ（2a）と（2b）のすべての文字列になります。

（3）基本ケースが必要です。 Nが0または1の場合、結果のリストは空になります。 N == 2の場合は、ただ1つの文字列、"cc"があります。 N == 3の場合は、ただ1つの文字列、"ddd"を持ちます。

ご注文は問題ではないため、必要に応じてリストの代わりにSetを使用することができます。

グローバルリストを使用するか、結果を保持することをお勧めします。メソッドが再帰的に呼び出され、メソッドの呼び出しがすべて同じリストまたはセットに接触すると、すべてが機能するようにしようとして狂ってしまいます。それぞれの再帰的な呼び出しに結果とともにローカルリストを保持させる方がずっと簡単です。 編集：これを明確にする必要があります。グローバル（すなわち、すべての再帰呼び出しで共有されるインスタンスフィールド）を保持するコレクションは、の最終の結果はOKです。しかし、上記で概説したアプローチでは、多くの中間結果が含まれています。長さが8のすべての文字列を検索する場合は、長さが6,5,4、...の文字列も検索されます。それらをすべて保持するためにグローバルを使用すると痛いでしょう。

Answer 2

set is returned emptyの理由は単にロジックに従ってください。

最初の反復strings(5,5,"");：あなたはstrings(5,5,"");実行されgenerateset(5);を実行すると言う(s.length() == size)を何もset

2回目の繰り返しstrings(2,5,"");に追加されていないので、偽です：(n == 3)さ：(n == 2)ので、何もset

3回目の繰り返しstrings(3,5,"");に追加されない、真でありますtrue、したがって何も追加されない 〜set

ged。