發現使用JavaScript

Question

我想有效地收集進一步的計算所有子陣列在javascript在O（n）的時間一維數組的所有子陣列。我不知道這是可能的，但似乎對於一個子數組和kadane公式爲O（n），這是比其他方法更有效。但我不確定我如何在每一步中存儲數組。

這個quora question類似，對我的僞代碼是不夠的。感謝您的進一步細分。

另一個meta link

一個在此動作例如[3,3，9,9，5]

[3], [9], [5], [9, 5], [9, 3], [9, 9], [3, 3], 
[3, 9, 9], [3, 3, 9], [9, 9, 5], [3, 3, 9, 9], 
[3, 9, 9, 5], [3, 3, 9, 9, 5] 

Answer 1

這是很簡單的事：https://jsfiddle.net/j1LuvxLq/

你要做的就是迭代可能lenghts和出發點和剛打印出來的子集。複雜度是O（n²），其中n是原始數組的長度。沒有辦法改善它的想法，因爲那是有多少個子集的順序。

var set = [3, 3, 9, 9, 5].join('') 

var set_length = set.length 

var subsets = [] 

for (var length_of_subset = 1; length_of_subset <= set_length; length_of_subset++) { 
    for (var start_of_subset = 0; start_of_subset <= set_length - length_of_subset; start_of_subset++) { 
     var current_subset = set.substring(start_of_subset, start_of_subset + length_of_subset) 
     if(subsets.indexOf(current_subset) == -1) { 
      subsets.push(current_subset.split('')) 
     } 
    } 
} 

// print the subsets out 
for (s in subsets) { 
    $('body').append(subsets[s].join(', ') + '<br>') 
} 

另一種可能更好的解決方案是使用動態編程。從3開始，刪除最後一個元素或添加下一個元素。看看這裏：https://jsfiddle.net/p82fcs4m/

var set = [3, 3, 9, 9, 5].join('') 
var subsets = [] 

take(set[0], set.substring(1)) 

function take(chosen, left) { 

    if(subsets.indexOf(chosen) != -1) { 
     return 
    } 

    subsets.push(chosen) 

    if (chosen.length > 1) { 
     take(chosen.substring(1), left) 
    } 

    if (left.length > 0) { 
     take(chosen.concat(left[0]), left.substring(1)) 
    } 
} 

$('body').append(subsets.join('<br>')) 

Answer 2

我已經做了工作先前計算的氨基酸總分子量的所有組合重量。如果你忽略空的那個，你應該有2^n-1個子陣列。所以這裏沒有O（n）。我有兩種方法作爲二進制和遞歸。

function getSubArrays(arr){ 
 
    var len = arr.length, 
 
    subs = Array(Math.pow(2,len)).fill(); 
 
    return subs.map((_,i) => { var j = -1, 
 
           k = i, 
 
           res = []; 
 
          while (++j < len) { 
 
           k & 1 && res.push(arr[j]); 
 
           k = k >> 1; 
 
          } 
 
          return res; 
 
          }).slice(1); 
 
} 
 

 
console.log(JSON.stringify(getSubArrays([1,2,3,4,5])));

function getSubArrays(arr){ 
 
    if (arr.length === 1) return [arr]; 
 
    else { 
 
    \t subarr = getSubArrays(arr.slice(1)); 
 
    \t return subarr.concat(subarr.map(e => e.concat(arr[0])), [[arr[0]]]); 
 
    } 
 
} 
 

 
console.log(JSON.stringify(getSubArrays([1,2,3,4,5])));

我不能設法得到超過23項的數組子陣列雖然。 這裏是表演。爲了安全起見，我嘗試了22個項目，首先是遞歸，然後是二元路線。

function getSubArrays(arr){ 
 
    if (arr.length === 1) return [arr]; 
 
    else { 
 
    \t subarr = getSubArrays(arr.slice(1)); 
 
    \t return subarr.concat(subarr.map(e => e.concat(arr[0])), [[arr[0]]]); 
 
    } 
 
} 
 

 

 
var aminos = Array(22).fill().map((_,i) => i+1), 
 
    subarrs = [], 
 
     ps = 0, 
 
     pe = 0; 
 
ps = performance.now(); 
 
subarrs = getSubArrays(aminos); 
 
pe = performance.now(); 
 
console.log("recursive route took: " + (pe-ps) + "msec to produce " + subarrs.length + " sub arrays");

function getSubArrays(arr){ 
 
    var len = arr.length, 
 
    subs = Array(Math.pow(2,len)).fill(); 
 
    return subs.map((_,i) => { var j = -1, 
 
           k = i, 
 
           res = []; 
 
          while (++j < len) { 
 
           k & 1 && res.push(arr[j]); 
 
           k = k >> 1; 
 
          } 
 
          return res; 
 
          }).slice(1); 
 
} 
 

 
var aminos = Array(22).fill().map((_,i) => i+1), 
 
    subarrs = [], 
 
     ps = 0, 
 
     pe = 0; 
 
ps = performance.now(); 
 
subarrs = getSubArrays(aminos); 
 
pe = performance.now(); 
 
console.log("binary route took: " + (pe-ps) + "msec to produce " + subarrs.length + " sub arrays");