的JavaScript - 生成一個數組的所有組合，考慮到爲了

-1

我有不同的陣列，全部用數字，而是用不同數量的元素：的JavaScript - 生成一個數組的所有組合，考慮到爲了

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

我需要得到每個陣列中的所有組合，但考慮元素順序。輸出元素的長度應始終與輸入數組相同。

該結果應該是數組的數組，像這樣：

爲AR1：

[2, 5] 
[5, 2]

爲AR2：

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

我不想一個笛卡爾乘積，每個數組應該自己處理。

到目前爲止，我發現的所有解決方案都只創建與順序無關的數組，因此ar1的結果只有一個數組而不是兩個。

解決方案應該適用於輸入數組中的任意數量的元素。我們可以假設輸入數組中沒有重複的值。

來源

2016-11-17 Ulli

http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/希望這能解決你的問題。 –

不知道這是最好的方式，但它似乎工作。 Nina的解決方案看起來很不錯，但它確實有一點數組concat &切片，所以這可能對更大的集合更好，因爲它避免了這種情況。我使用一個對象進行重複檢查，但hashmaps在JS中超級快。

只是好奇，性能測試也是如此。做[1,2,3,4,5,6,7]，使用@妮娜的解決方案花費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');

來源

2016-11-17 13:04:07 Keith

請看看我的結果，關於性能，我得到8毫秒以下的東西，你的需要大約360毫秒。 –

@NinaScholz尼斯更新，我的表現測試是在你原來的..我想我想和你結婚:)，我全部爲你得到接受答案btw ..你怎麼沒有投票給主持人選舉。你會得到我的投票。聰明而沒有態度.. – Keith

您可以使用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; }

來源

2016-11-17 12:58:12

的JavaScript - 生成一個數組的所有組合，考慮到爲了

回答

相關問題