JavaScriptを - 私はすべての数字と異なるアレイを、持っているが、要素の数が異なるため

Question

を考慮すると、配列のすべての組み合わせを生成：

var ar1 = [2, 5]; 
var ar2 = [1, 2, 3]; 

私は各アレイのすべての組み合わせを取得する必要がありますが、考えます要素の順序出力要素の長さは常に入力配列と同じでなければなりません。

このように、この結果は、配列の配列でなければなりません：AR1のための

：AR2について

[2, 5] 
[5, 2] 

：

[1, 2, 3] 
[1, 3, 2] 
[2, 1, 3] 
[2, 3, 1] 
[3, 1, 2] 
[3, 2, 1] 

私はそれぞれ、デカルト積を望んでいません配列はそれ自身で処理する必要があります。

私が今までに見つけたすべての解決策は、順序に依存しない配列しか作成していないので、ar1の結果は2つではなく1つの配列になります。

解決策は、入力配列の任意の数の要素に対して機能するはずです。入力配列に値が重複していないと仮定できます。

Answer 1

、これが最良の方法ですが、動作しているようならばわかりません。

@ Ninaの解決策はうまく見えますが、配列concat &スライスのかなりのビットがあります。そのため、大きなセットではそれが回避されるため、より効果的です。重複チェックにはオブジェクトを使用しますが、ハッシュマップはJSで非常に高速です。

好奇心が強いので、パフォーマンステストも行いました。 [1,2,3,4,5,6,7]を実行すると、@ Ninaのソリューションの取得時間は38.8秒です。 私はtoke 175msをやっている..配列concat/sliceは大規模なパフォーマンスヒットであり、マークされた重複は同じ問題を抱えています。ただ知っておくべきこと。

var ar1 = [2, 5]; 
 
var ar2 = [1, 2, 3]; 
 

 
function combo(c) { 
 
    var r = [], 
 
     len = c.length; 
 
     tmp = []; 
 
    function nodup() { 
 
    var got = {}; 
 
    for (var l = 0; l < tmp.length; l++) { 
 
     if (got[tmp[l]]) return false; 
 
     got[tmp[l]] = true; 
 
    } 
 
    return true; 
 
    } 
 
    function iter(col,done) {  
 
    var l, rr; 
 
    if (col === len) {  
 
     if (nodup()) { 
 
     rr = []; 
 
     for (l = 0; l < tmp.length; l++) 
 
      rr.push(c[tmp[l]]);   
 
     r.push(rr); 
 
     } 
 
    } else { 
 
     for (l = 0; l < len; l ++) {    
 
     tmp[col] = l; 
 
     iter(col +1); 
 
     } 
 
    } 
 
    } 
 
    iter(0); 
 
    return r; 
 
} 
 

 
console.log(JSON.stringify(combo(ar1))); 
 
console.log(JSON.stringify(combo(ar2))); 
 
console.log('something bigger [1,2,3,4,5,6,7]'); 
 
console.time('t1'); 
 
combo([1,2,3,4,5,6,7]); 
 
console.timeEnd('t1');

Answer 2

permutationには、それ以上要素が継承されなくなるまで繰り返しと再帰的アプローチを使用できます。

function permutation(array) { 
 
    function p(array, temp) { 
 
     var i, x; 
 
     array.length || result.push(temp); 
 
     for (i = 0; i < array.length; i++) { 
 
      x = array.splice(i, 1)[0]; 
 
      p(array, temp.concat(x)); 
 
      array.splice(i, 0, x); 
 
     } 
 
    } 
 

 
    var result = []; 
 
    p(array, []); 
 
    return result; 
 
} 
 

 
console.log('something bigger [1,2,3,4,5,6,7]'); 
 
console.time('t1'); 
 
permutation([1, 2, 3, 4, 5, 6, 7]); 
 
console.timeEnd('t1'); 
 

 
console.log(permutation([2, 5])); 
 
console.log(permutation([1, 2, 3]));

.as-console-wrapper { max-height: 100% !important; top: 0; }