javascript를 사용하여 o (n) 시간 1D 배열의 모든 하위 어레이를 찾습니다.

Question

자바 스크립트에서 추가 계산을 위해 모든 하위 어레이를 효율적으로 수집하려고합니다. 이것이 가능하다고 확신 할 수는 없지만 부분 배열에 대한 것입니다. kadane의 수식은 다른 방법보다 효율적입니다. 하지만 각 단계마다 배열을 저장할 수있는 방법이 확실하지 않습니다.

유사 코드 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/

을 그냥 하위 집합을 인쇄 . 복잡도는 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

I 이전 분자 총 아미노산의 모든 조합을 계산하는 작업을 행한 무게. 비어있는 것을 무시한다면 2^n - 1 개의 서브 배열이 있어야합니다. 그래서 여기서 O (n)은 없습니다. 바이너리와 재귀로 두 가지 방법이 있습니다.

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 개 이상의 항목 배열의 하위 어레이를 얻을 관리 할 수 ​​

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

. 다음은 공연입니다. 안전 측면에 있으려면 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");