ループのネスト - 特定の組み合わせを無視するにはどうすればよいですか？

Question

私はある種のブルートフォース攻撃をして問題を解決しています。理論的にはそれは実用的な解決策ですが、実際にはそうですが、時間がかかります。

私はお互いに7つのネストされたループを持っていますが、何も繰り返されない 'for変数'の組み合わせが必要です。だから1,2,3,4,5,6,7は許可されますが、1,1,3,4,5,6,7は無視してください。私は現在、配列内の重複する項目をチェックする機能を使用しています：私はすぐにそれらの組み合わせを無視する代わりのために何度もその機能を使用してすることができれば、私はしたほうが良いと思うしかし

http://www.groggyjava.tv/freebies/duplicates.html

すべて単一の組み合わせ。今私は14^7 = 105.413.504の組み合わせを評価していますが、14 nPr 7 = 17.297.280しか必要ではありません。

私のコードは、現在（HGDが重複しない場合にtrueを返しますと、重複したテスト機能である）である：

for(var a=0;a<14;a++) { 
    for(var b=0;b<14;b++) {if(hgd([a,b])) { 
     for(var c=0;c<14;c++) {if(hgd([a,b,c])) { 
      for(var d=0;d<14;d++) {if(hgd([a,b,c,d])) { 
       for(var e=0;e<14;e++) {if(hgd([a,b,c,d,e])) { 
        for(var f=0;f<14;f++) {if(hgd([a,b,c,d,e,f])) { 
         for(var g=0;g<14;g++) {if(hgd([a,b,c,d,e,f,g])) { 
          check([a,b,c,d,e,f,g]); 
         }} 
        }} 
       }} 
      }} 
     }} 
    }} 
} 

どのように私はこれを高速化することができ、ループのための別の解決策の代わりには、おそらくありますか？

ありがとうございました。

Answer 1

はすべて順列14個の控えめな値のリストのを反復処理されます。

一般的に、慎重なもののリストのすべての順列を訪問するには、リストの各要素を参照します。各要素について、元のリストの他の要素をすべて含む新しいリストを作成します。 のすべての順列をリストに追加し、それぞれに要素を追加すると、その特定の要素で始まる元のリストのすべての順列が得られます。あなたがすべての要素を完了したら、あなたは完了です。

リスト内の1つの要素を含むリストのすべての順列を見つけることは、もちろん単純な作業です。どのようなことがないことは、再帰的に私は、上記の操作を行っている

function forEachPermutation(list, operation) { 
    function pluckElement(list, index) { 
    var e = list[index]; 
    var l = []; 
    for (var i = 0; i < list.length; ++i) 
     if (i !== index) l.push(list[i]); 
    return { element: e, remainder: l }; 
    } 

    function permute(partial, remainder) { 
    if (remainder.length === 0) 
     operation(partial); 
    else { 
     for (var i = 0; i < remainder.length; ++i) { 
     var plucked = pluckElement(remainder, i); 
     partial.push(plucked.element); 
     permute(partial, plucked.remainder); 
     partial.length--; 
     } 
    } 
    } 

    permute([], list); 
} 

：

したがって、私たちが持っていることは、このようなものです。 "pluckElement"関数はリストから要素を返し、はそのリストのを返します。 "permute"関数は、元のリストの完全な順列に渡された操作を実行するか（残ったリストが空であることに気づいたとき）、またはそれが渡されたリストの各要素を使って再帰的に自身を呼び出します。

は、その機能を使用するには、あなただけのこの操作を行うと思います。

forEachPermutation([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], check); 

編集 —を使用すると、元のリストから値のみ一定数を摘採したい場合は、上記に持っています変更される;ちょっと待って。

OK - 14個の要素のリストを渡したいが、14個の別個のリスト（たとえば7個）ごとに "operation"関数が呼び出されるようにするには、次のように関数を変更することができます。外側の "forEachPermutation"関数は、追加の "len"パラメータを取り、必要な文字列の長さを指示します。次に、 "permute"関数は、空の剰余をチェックするのではなく、 "partial.length"がそのターゲット長であるかどうかをチェックします。

function forEachPermutation(list, len, operation) { 
    function pluckElement(list, index) { 
    var e = list[index]; 
    var l = []; 
    for (var i = 0; i < list.length; ++i) 
     if (i !== index) l.push(list[i]); 
    return { element: e, remainder: l }; 
    } 

    function permute(partial, remainder) { 
    if (partial.length === len) 
     operation(partial); 
    else { 
     for (var i = 0; i < remainder.length; ++i) { 
     var plucked = pluckElement(remainder, i); 
     partial.push(plucked.element); 
     permute(partial, plucked.remainder); 
     partial.length--; 
     } 
    } 
    } 

    permute([], list); 
} 

と「操作」機能は、それぞれ1を処理した後、何らかの理由であなたが保存順列にしたい場合は、我々はその後、別の編集 —

forEachPermutation([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], 7, check); 

とそれを呼びたいです使用されている部分配列が上書きされるという事実を考慮する必要があります。 「操作」への呼び出しを変更することができます：「操作」の各呼び出しは、使用するその非常に自身の配列を取得するように、「部分的」配列のコピーを作成します

if (partial.length === len) 
    operation(partial.slice(0)); 

を。もちろん、それはプロセスを遅くします。

Answer 2

問題は余分な作業をしていることです。あなたのcループでは、すでにaとbが等しくないことはわかっていますが、とにかくチェックします。

for(var a=0;a<14;a++) { 
    for(var b=0;b<14 && b!=a;b++) { 
     for(var c=0;c<14 && c!=a && c!=b;c++) { 
      ... 
     } 
    } 
} 

これは、内側のループで少し冗長を取得しますが、少なくとも単純です：あなたは、c-スタイルforループの柔軟性を悪用する可能性があります。あなたはここで何をやっている