11

Javaでワードアンスクランブラーを作っています。現在、3文字以上の単語から選択された3文字のすべての再配置を印刷できるプログラムがあります（繰り返しはありません）。たとえば、パラメーターがabcdの場合、次のように出力されます。

[[abc, abd, acb, acd, adb, adc, bac, bad, bca, bcd, bda, bdc, cab, cad, cba, cbd, cda, cdb, dab, dac, dba, dbc, dca, dcb] ]

順列で 2D 配列リストを埋めています。現在、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);
}

私は他の投稿を見てきましたが、再帰がこれを解決できると聞きました。ただし、それをどのように実装するかはわかりません。また、理解できない複雑なソリューションもいくつか見てきました。再帰を伴うかどうかにかかわらず、可能な限り簡単な解決策を求めています。

4

3 に答える 3

5

再帰的な方法では、ループの 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);
            }
        }
    }
}
于 2013-08-10T20:17:44.920 に答える