0

組み合わせで数字を複製せずに、0から6までの数字の可能な組み合わせごとにテストを実行する必要があるjavascriptアプリケーションがあります。

つまり: 0123456、0123465、0123546、0123564 ...

(ただし、たとえば 0123455 は 5 が重複しているため含めないでください)

私はそれを繰り返し行いました:

function testAllCombinations(){
    for(var i = 0; i < 7; i++){
        for(var j = 0; j < 7; j++){
            if(j == i)
                continue;
            for(var k = 0; k < 7; k++){
                if(k == j || k == i)
                    continue;
                for(var l = 0; l < 7; l++){
                    if(l == k || l == j || l == i)
                        continue;
                    for(var m = 0; m < 7; m++){
                        if(m == l || m == k || m == j || m == i)
                            continue;
                        for(var n = 0; n < 7; n++){
                            if(n == m || n == l || n == k || n == j || n == i)
                                continue;
                            for(var o = 0; o < 7; o++){
                                if(o == n || o == m || o == l || o == l || o == j || o == i)
                                    continue;

                                runTest(i, j, k, l, m, n, o);
                            }
                        }
                    }
                }
            }
        }
    }
}

それはうまくいきますが、再帰的にやりたいのですが、アルゴリズムを構築するのに本当に苦労しています。

誰かが私に方向性を教えてもらえますか?

前もって感謝します。

4

2 に答える 2

4

これは、再帰に関する一般的な質問のようです。

再帰アルゴリズムは、基本ケースと再帰ケースの 2 つの部分に分けることができます。最初に、再帰を必要としない単純な結果をもたらす基本ケースを把握します。基本ケースになる入力が複数ある場合があります。最も些細な入力から始めて、そこから拡張します。すぐに、再帰関数の重要な要素である再帰ケースを見つけることができます。再帰的なケースはすべて、基本ケースを含む以前のケースで構成された同様のパターンを使用して解決できることがわかります。

この問題のために、ユーザーが文字列を入力でき、文字列内のすべての文字の組み合わせを出力したいとしましょう。この呼び出しを f(s) と呼びましょう。ユーザーが長さ 0 または 1 の文字列を入力した場合、使用可能な組み合わせは 1 つしかないため、単に指定された文字列を返します。ここでは特別なことは何もありません。これがベースケースです。

ユーザーが長さ 2 の文字列 (例: "01") を入力した場合、考えられる組み合わせは "01" と "10" であることは明らかです。どうやってこの答えを得たのですか?
"01" = "0" + "1" および "10" = "1" + "0" であることに注意してください。
つまり、各数値をループし、それを f(s) の結果と結合しました。ここで、s = 残りの数値です。
すなわち。"01" = "0" + f("1") および "10" = "1" + f("0")。
長さが 1 の場合にこの問題を解決する方法は既にわかっているので、入力の長さが 2 の場合に問題を解決する方法もわかりました。

入力の長さが 3 (例: "012") の場合、答えは "012"、"021"、"102"、"120"、"201"、"210" であることがわかります。
"012"、"021" = "0" + "12"、"0" + "21" および "102"、"120" = "1" + "02"、"1" + "20"、および "201", "210" = "2" + "01", "2" + "10" つまり、各数値をループし、それを f(s) の結果と結合しました。ここで、s = 残りの数値です。おなじみですか?
すなわち。"012"、"021" = "0" + f("12") および "102"、"120" = "1" + f("02") および "201"、"210" = "2" + f("

今、パターンが見えますか?各レベル (入力の長さ) で同じ原則を適用するため、問題のサブセットに対して同じコード片を何度も利用し、最終的にそれらをまとめて最終的な答えを形成することができます。これが再帰を非常にエレガントにするものです。

入力の長さが 4 の場合、同じパターンをもう一度適用できることに注意してください。
すなわち。f("0123") = "0" + f("123")、"1" + f("023")、"2" + f("013")、"3" + f("012")であり、長さが 3 の場合にこの問題を解決する方法は既にわかっているので、入力の長さが 4 の場合に問題を解決する方法がわかりました。

続けて、コードで解決策を書き出すこともできますが、再帰を学習するためのより良いリソースが他にあることは間違いありません。ただし、(願わくば)私の説明は、あなたが正しい方向に考え、追加のリソースを読まなくても問題を解決するのに十分です。

再帰に取り組むための鍵は、最も単純なケースから始めて、そこから構築することであることを覚えておいてください。

于 2013-09-14T06:20:02.130 に答える