使用 javascript 在 o(n) 时间一维数组中查找所有子数组

Question

我想收集所有子数组以便在 javascript 中高效地进行进一步计算。我不确定这是可能的，但对于子数组和 kadane 的公式似乎是 o(n)，它比其他方法更有效。但我不确定如何在每一步存储数组。

与此类似quora question，对我来说伪代码还不够。感谢您的进一步细分。

[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

我之前做过一个计算所有氨基酸组合总分子量的工作。如果你忽略空的，你应该有 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 {
   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])));

虽然我无法获取包含超过 23 个项目的数组的子数组。以下是表演。为了安全起见，我尝试使用 22 个项目，首先使用递归，然后使用二进制路由。

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

Answer 2

这很简单：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 3

我相信使用 Array.slice 是最干净的方法，不是吗？

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;
}

使用 javascript 在 o(n) 时间一维数组中查找所有子数组

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

javascript

arrays

algorithm

kadanes-algorithm