find all subarrays in o(n) time 1D array using javascript - Stack Overflow

admin管理员组

文章数量:1332351

I want to collect all subarrays for further putation efficiently in javascript. I'm not sure this is possible, but it seems for a subarray sum kadane's formula is o(n) which is more efficient than other methods. But I'm not sure I how I can store the array at each step.

Similar to this quora question, for me the pseudo code was not enough. Thanks for the further breakdown.

another meta link

an example in action of this for [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]

I want to collect all subarrays for further putation efficiently in javascript. I'm not sure this is possible, but it seems for a subarray sum kadane's formula is o(n) which is more efficient than other methods. But I'm not sure I how I can store the array at each step.

Similar to this quora question, for me the pseudo code was not enough. Thanks for the further breakdown.

another meta link

an example in action of this for [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]

• javascript
• arrays
• algorithm
• kadanes-algorithm

Share Improve this question Follow edited Apr 12, 2017 at 7:31 CommunityBot 111 silver badge asked Sep 16, 2016 at 6:45 mibbitmibbit 5,37544 gold badges2828 silver badges3434 bronze badges 7

• can you add some examples, what you mean? – Nina Scholz Commented Sep 16, 2016 at 6:46
• Do you want the sum of all values in all subarrays? Or the actual subarrays themselves (that will be more costly than O(n))? – Thilo Commented Sep 16, 2016 at 6:48
• 1 There are O(n^2) subarrays. Any algorithm based on explicitly going over all subarrays can never be more efficient than O(n^2). That's usually not good enough. – user2357112 Commented Sep 16, 2016 at 6:52
• 1 The number of subarrays is n+(n-1)+...+1, which is roughly n^2/2. If you want all the actual subarrays, that means you will have to make O(n^2) memory operations. – Regis Portalez Commented Sep 16, 2016 at 6:56
• 2 I think you misunderstood the kadane's algorithm, it is for getting the maximum sum of subarrays, which is inherently different problem as yours – Tan Li Hau Commented Sep 16, 2016 at 6:56

 |  Show 2 more ments

4 Answers 4

Sorted by: Reset to default 4

I had done a work previously to calculate all binations of amino acids total molecular weight. If you neglect the empty one you should have 2^n - 1 sub arrays. So there is no O(n) here. I've got two methods as binary and recursive.

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 {
  	subarr = getSubArrays(arr.slice(1));
  	return subarr.concat(subarr.map(e => e.concat(arr[0])), [[arr[0]]]);
  }
}

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

I couldn't manage to get subarrays of an array with more than 23 items though. Here are the performances. To be on the safe side i try with 22 items, first with recursive and then with binary route.

function getSubArrays(arr){
  if (arr.length === 1) return [arr];
  else {
  	subarr = getSubArrays(arr.slice(1));
  	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");

This is fairly simple to do: https://jsfiddle/j1LuvxLq/

All you do is iterate possible lenghts and starting points and just print out the subsets. Complexity is O(n²) where n is the length of the original array. No way to improve it thought because that's the order of how many subsets there are.

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>')
}

Alternative, possibly nicer solution would be to use dynamic programming. Start with 3 and either remove last element or add next element. Check it out here: https://jsfiddle/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>'))

Try this:

function getSubArrays(arr) {
  const subArrays = [];
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i; j++) {
      const subArray = arr.slice(i, j + i + 1);
      subArrays.push(subArray);
    }
  }
}

Still O(n²) tho

I believe using Array.slice is the most clean way to do it, isn't it?

function getSubArrays(arr) {
    const subArrays = [];
    for (var i = 0; i < arr.length; i++) {
        for (var j = i; j < arr.length; j++) {
            subArrays.push(arr.slice(i, j + 1));
        }
    }
    return subArrays;
}

本文标签： find all subarrays in o(n) time 1D array using javascriptStack Overflow