入れ子にされたForループの変数番号

Question

私はjavaで単語解読をしています。今私は、3文字以上の単語（繰り返しなし）から選択された3文字のすべての並び替えを印刷できるプログラムを持っています。

[[ABC、ABD、ACB、ACD、ADB、ADC、BAC、悪い、BCA、BCD、BDA、BDC、タクシー、CAD：パラメータはABCDであれば、たとえば、これを印刷しますdac、dba、dbc、dca、dcb]]

私は2次元配列のリストを順列で埋めています。現在、2D配列には3つの文字の順列が含まれている配列が1つしかありません。私は、2D配列に、1文字、2文字、3文字などのように、単語の長さで停止する配列を持たせたい。問題は、これを達成するためにネストされたforループの可変数が必要なことです。 3文字の置換の場合、私は3つのforループを持っています。それぞれがパラメータの文字を循環します。

public static void printAllPermuations(String word) 
{ 
    int len = word.length(); 
    ArrayList<String> lets = new ArrayList<String>(); 
    //this array of letters allows for easier access 
    //so I don't have to keep substringing 
    for (int i = 0; i < len; i++) 
    { 
     lets.add(word.substring(i, i + 1)); 
    } 

    ArrayList<ArrayList<String>> newWords = new ArrayList<ArrayList<String>>(); 
    newWords.add(new ArrayList<String>()); 
    for (int i = 0; i < len; i++) 
    { 
     for (int j = 0; j < len; j++) 
     { 
      for (int k = 0; k < len; k++) 
      { 
       if (i != j && i != k && j != k) 
       //prevents repeats by making sure all indices are different 
       { 
        newWords.get(0).add(lets.get(i) + lets.get(j) + lets.get(k)); 
       } 
      } 
     } 
    } 
    System.out.println(newWords); 
} 

私は他の投稿を見てきましたが、私は再帰がこれを解決できると聞いてきました。私はそれをどのように実装するのか分かりません。私は理解していない複雑な解決策もいくつか見てきました。私は、再帰を含むかどうかに関わらず、の最も簡単な解決策を要求しています。

Answer 1

再帰的な方法では、関数のループの1つをループパラメータをその関数に渡します。次に、関数のループ内から別のループをネストするように呼び出します。

void loopFunction(ArrayList<ArrayList<String>> newWords, int level) { 
    if (level == 0) { // terminating condition 
     if (/* compare the indices by for example passing down a list with them in */) 
     { 
      newWords.get(...).add(...); 
     } 
    } else {// inductive condition 
     for (int i = 0; i < len; i++) { 
      loopFunction(newWords, level-1); 
     } 
    } 
} 

あなたが再帰を開始するので、だからあなたたとえば、あなたが再帰の3つのレベルが必要になります。

loopFunction(newWords, 3); 

編集

あなたはここに問題を抱えてきたので、作業バージョンです。それは比較するインデックスのリストを保持し、それが行くにつれて文字列を構築します。並べ替えられた単語は、各レベルで2D配列に追加され、単語の長さがすべて取得されます。再帰では、関数的に考えるのが最も簡単で、変数を変更することはできず、変数は不変（変更不可）にしておきます。便宜のために新しいコピーを作成するのではなく、indicesを更新しますが、このコードは主にそのコードを実行します。

void loopFunction(ArrayList<String> lets, ArrayList<ArrayList<String>> newWords, int level, ArrayList<Integer> indices, String word) { 
    if (level == 0) { // terminating condition 
     return; 
    } else { // inductive condition 
     for (int i = 0; i < lets.size(); i++) { 
      if (!indices.contains(i)) { // Make sure no index is equal 
       int nextLevel = level-1; 
       String nextWord = word+lets.get(i); 

       newWords.get(level-1).add(nextWord); 

       indices.add(i); 
       loopFunction(lets, newWords, nextLevel, indices, nextWord); 
       indices.remove((Integer) i); 
      } 
     } 
    } 
} 

Answer 2

私はあなたの実際のコードを与えることはありませんが、これはあなたの再帰が（私は再帰的にそれを行うには、他の方法があると信じて：P）のように見えることができる方法のアイデア与える必要があり

void findAllCombination(String tmpResult, 
         String rawString, 
         int noOfChar, 
         List<String> allCombinations) { 
    if (tmpResult.size() == noOfChar) { 
    allCombinations.add(tmpResult); 
    } else { 
    for (i in 0 to rawString.size()) { 
     findAllCombination(tmpResult + rawString[i], 
         rawString.removeCharAt(i), 
         noOfChar, 
         allCombinations); 
    } 
    } 
} 

List<String> foo(String input, int level) { 
    List<String> allResults = ...; 
    findAllCombination("", input, level, allResults); 
    return allResults; 
} 

を主な再帰部分はfindAllCombinationです。アイデアは厳しいものです。すべての置換を見つける方法は、私たちが持っているrawStringの入力に対して、文字を1つずつ取り出して、以前に見つかったtmpResultに追加し、そのtmpResultを使用してさらに処理します。いったんtmpResultが十分に長い点に達すると、tmpResultを結果のallCombinationsリストに置きます。

（FOO（）メソッドは、ちょうどあなたの呼び出しを容易にするためにここにある：実際に作業を行うPコードはわずか6行である、唯一のブラケットでラインを除くと、私は読みやすくするため、意図的に破るラインを無視して）

Answer 3

@DrYapが言ったことに基づいて、私はこれ（それが彼よりも少し違う）を書いた：

をここでそれを開始するためのコードされています

for(int i = 1; i <= len; i++) 
{ 
    newWords.add(new ArrayList<String>()); 
    loop(i); 
} 

をここでは、ループ方式です。多くの変数がインスタンス変数として宣言されているため、パラメータに渡す必要はありません。

public static void loop(int level) 
{ 
    if (level == 0) 
    { 
     int pos = indices.size() - 1; 
     int pos2 = newWords.get(pos).size(); 
     newWords.get(pos).add(""); 
     for (Integer letIndex : indices) 
     { 
      String previous = newWords.get(pos).get(pos2); 
      newWords.get(pos).set(pos2, previous + lets.get(letIndex)); 
     } 
    } 
    else 
    { 
     for (int i = 0; i < len; i++) 
     { 
      if (!indices.contains(i)) 
      { 
       int indicesIndex = indices.size(); 

       indices.add((Integer) i); 
       loop(level - 1); 
       indices.remove(indicesIndex); 
      } 
     } 
    } 
}