javascriptを使用してo（n）時間1D配列内のすべてのサブアレイを見つける

Question

さらなる計算のためにすべてのサブアレイをJavascriptで効率的に収集したい。私はこれが可能であるかどうかはわかりませんが、サブアレイの和はkadaneの式が他の方法よりも効率的なo（n）であるようです。しかし、私はどのように私は各ステップで配列を格納することができますか分からない。

quora questionと同様に、私にとっては疑似コードでは十分ではありませんでした。さらなる故障をありがとう。 I分子の総アミノ酸の全ての組み合わせを計算するために、以前に作業を行っていた[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

ため、この作用で

別meta link

例重量。あなたが空のものを無視するなら、2^n - 1個のサブ配列が必要です。ここにはO（n）はありません。バイナリと再帰の2つのメソッドがあります。

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");