过滤掉二维数组中可以由该二维数组中的其他数组组成的数组

Question

所以，假设我们有一个数组数组，arr arr = [[1], [3], [1, 3]] 现在，我们想要找到 arr 的一个子集，它将过滤掉所有元素都可以在其他数组中找到的数组，优化输出中的数组数量最少。在上面的例子中，我们会得到 [[1, 3]]。现在，这并不太难，但我希望它能够扩展。比如说，如果我有 60 个数组，每个数组最多包含 70 个元素。

这是我尝试的解决方案：

const x = [[1], [3], [1, 3]] 递归查找最短解法(x, x.flat())

function recursiveFindShortestSolution(array, allElements){
    if(array.length === 0){
        return null
    }
    if(!oneArrayContainsAll2DArray(allElements, array)){
        return null
    }
    let solution = array
    for(let i = 0; i < array.length; i++){
        const childSolution = recursiveFindShortestSolution([...array.slice(0, i), ...array.slice(i+1)], allElements)
        if(childSolution){
            solution = childSolution
        }
    }
    return solution
}

function oneArrayContainsAll2DArray(oneDArray, twoDArray){
    const flatTwoDArray = twoDArray.flat()
    if(oneDArray.every((element)=>{
        return flatTwoDArray.includes(element)
    })){
        return true
    }
    return false
}

现在，很明显，这需要很长时间才能运行在我需要的复杂事物上。我知道动态规划应该可以帮助我进行优化，但我只是遇到了堆溢出。如果有人有的话。优化技巧，将不胜感激。这是我的测试数据：

[
  [ 32, 33 ],
  [ 34, 32, 35, 33 ],
  [ 36, 32, 37, 33 ],
  [ 40, 32, 41, 33 ],
  [ 48, 32, 49, 33 ],
  [ 96, 32, 97, 33 ],
  [ 162, 34, 163, 35 ],
  [ 224, 96, 225, 97 ],
  [ 191, 63, 183, 55 ],
  [ 239, 111, 231, 103 ],
  [
    38, 34, 36, 32,
    39, 35, 37, 33
  ],
  [
    42, 34, 40, 32,
    43, 35, 41, 33
  ],
  [
    44, 36, 40, 32,
    45, 37, 41, 33
  ],
  [
    50, 34, 48, 32,
    51, 35, 49, 33
  ],
  [
    52, 36, 48, 32,
    53, 37, 49, 33
  ],
  [
    56, 40, 48, 32,
    57, 41, 49, 33
  ],
  [
    98, 34, 96, 32,
    99, 35, 97, 33
  ],
  [
    100, 36, 96, 32,
    101, 37, 97, 33
  ],
  [
    104, 40, 96, 32,
    105, 41, 97, 33
  ],
  [
    112, 48, 96, 32,
    113, 49, 97, 33
  ],
  [
    166, 38, 162, 34,
    167, 39, 163, 35
  ],
  [
    170, 42, 162, 34,
    171, 43, 163, 35
  ],
  [
    178, 50, 162, 34,
    179, 51, 163, 35
  ],
  [
    226, 98, 162, 34,
    227, 99, 163, 35
  ],
  [
    228, 100, 224, 96,
    229, 101, 225, 97
  ],
  [
    240, 112, 224, 96,
    241, 113, 225, 97
  ],
  [
    174, 46, 166, 38,
    170, 42, 162, 34
  ],
  [
    248, 120, 240,
    112, 249, 121,
    241, 113
  ],
  [
    255, 127, 191, 63,
    247, 119, 183, 55
  ],
  [
    46, 38, 42, 34, 44, 36,
    40, 32, 47, 39, 43, 35,
    45, 37, 41, 33
  ],
  [
    54, 38, 50, 34, 52, 36,
    48, 32, 55, 39, 51, 35,
    53, 37, 49, 33
  ],
  [
    58, 42, 50, 34, 56, 40,
    48, 32, 59, 43, 51, 35,
    57, 41, 49, 33
  ],
  [
    60, 44, 52, 36, 56, 40,
    48, 32, 61, 45, 53, 37,
    57, 41, 49, 33
  ],
  [
    102, 38,  98, 34, 100, 36,
     96, 32, 103, 39,  99, 35,
    101, 37,  97, 33
  ],
  [
    106, 42,  98, 34, 104, 40,
     96, 32, 107, 43,  99, 35,
    105, 41,  97, 33
  ],
  [
    108, 44, 100, 36, 104, 40,
     96, 32, 109, 45, 101, 37,
    105, 41,  97, 33
  ],
  [
    114, 50,  98, 34, 112, 48,
     96, 32, 115, 51,  99, 35,
    113, 49,  97, 33
  ],
  [
    116, 52, 100, 36, 112, 48,
     96, 32, 117, 53, 101, 37,
    113, 49,  97, 33
  ],
  [
    120, 56, 104, 40, 112, 48,
     96, 32, 121, 57, 105, 41,
    113, 49,  97, 33
  ],
  [
    182, 54, 166, 38, 178, 50,
    162, 34, 183, 55, 167, 39,
    179, 51, 163, 35
  ],
  [
    186, 58, 170, 42, 178, 50,
    162, 34, 187, 59, 171, 43,
    179, 51, 163, 35
  ],
  [
    230, 102, 166,  38, 226,
     98, 162,  34, 231, 103,
    167,  39, 227,  99, 163,
     35
  ],
  [
    234, 106, 170,  42, 226,
     98, 162,  34, 235, 107,
    171,  43, 227,  99, 163,
     35
  ],
  [
    242, 114, 178,  50, 226,
     98, 162,  34, 243, 115,
    179,  51, 227,  99, 163,
     35
  ],
  [
    244, 116, 228, 100, 240,
    112, 224,  96, 245, 117,
    229, 101, 241, 113, 225,
     97
  ],
  [
    190, 62, 174, 46, 182, 54,
    166, 38, 186, 58, 170, 42,
    178, 50, 162, 34
  ],
  [
    238, 110, 174,  46, 230,
    102, 166,  38, 234, 106,
    170,  42, 226,  98, 162,
     34
  ],
  [
    252, 124, 244, 116,
    248, 120, 240, 112,
    253, 125, 245, 117,
    249, 121, 241, 113
  ],
  [
    246, 118, 182,  54, 230, 102, 166,
     38, 242, 114, 178,  50, 226,  98,
    162,  34, 247, 119, 183,  55, 231,
    103, 167,  39, 243, 115, 179,  51,
    227,  99, 163,  35
  ],
  [
    250, 122, 186,  58, 234, 106, 170,
     42, 242, 114, 178,  50, 226,  98,
    162,  34, 251, 123, 187,  59, 235,
    107, 171,  43, 243, 115, 179,  51,
    227,  99, 163,  35
  ],
  [
    254, 126, 190,  62, 238, 110, 174,
     46, 246, 118, 182,  54, 230, 102,
    166,  38, 250, 122, 186,  58, 234,
    106, 170,  42, 242, 114, 178,  50,
    226,  98, 162,  34
  ],
  [
    126,  62, 110,  46, 118,  54, 102,  38, 122,  58, 106,
     42, 114,  50,  98,  34, 124,  60, 108,  44, 116,  52,
    100,  36, 120,  56, 104,  40, 112,  48,  96,  32, 127,
     63, 111,  47, 119,  55, 103,  39, 123,  59, 107,  43,
    115,  51,  99,  35, 125,  61, 109,  45, 117,  53, 101,
     37, 121,  57, 105,  41, 113,  49,  97,  33
  ]
]

Answer 1

您可以使用带有

reduce()

和

filter()

方法的功能方法，使用很少的辅助函数。

filterSubsets

函数使用

reduce

创建一个新数组。它检查测试的子数组是否唯一，如果是，则将其添加到累积数组中。然后过滤结果数组以排除任何作为其他数组子集的数组。

const arr = [[1], [3], [1, 3]];


// check if arr1 is a subset of arr2
const isSubset = (arr1, arr2) => arr1.every(elem => arr2.includes(elem));

// check if arr1 is equal to arr2
const isEqual = (arr1, arr2) => arr1.length === arr2.length && arr1.every((elem, idx) => elem === arr2[idx]);

// check if arr1 is unique
const isUnique = (arr1, arrList) => !arrList.some(existingArr => isEqual(arr1, existingArr) || isSubset(arr1, existingArr));

// returns arrays that are not subsets of any other arrays
const filterSubsets = (arrList) =>
  arrList.reduce((acc, arr) => (isUnique(arr, acc) ? acc.concat([arr]) : acc), [])
         .filter((arr, index, arrList) =>
           !arrList.some((superArr, superIndex) => superIndex !== index && isSubset(arr, superArr)));

console.log(filterSubsets(arr));