javascript - 如何在数组数组中查找和提取所有重复的子集？

Question

我有这个数组，其中包含两个子集 7,8 和 1 两次:

[
  [1,2],
  [9,10,7,8],
  [5,6,7,8],
  [1]
]

我如何找到并提取此数组中的所有子集(包含不止一次，即除自身以外)并获得以下结果？

[
  [2],
  [9,10],
  [7,8],
  [5,6],
  [1]
]

子集总是连续的，即 9,7 不应被视为 9,10,7,8 的子集。

编辑:最终数组的顺序无关紧要，但项目应与起始数组中的一样:

  ok=[               ok=[            notOk=[
      [2],               [9,10],            [10,9],
      [9,10],            [2],               [2],
      [7,8],             [5,6],             [6,5],
      [5,6],             [1],               [1],
      [1]                [7,8]              [8,7]
    ]                  ]                   ]

任何非递归解决方案将不胜感激。

Answer 1

我提出了这个解决方案，它为每个不同的值构建一个映射(散列)，为其提供一个出现的数组。每个这样的数组元素提供值出现的子数组(来自输入)及其在该子数组中的索引。

在第二步中，比较等值元素的后继元素。如果那些也都是相同的，并且该值没有出现在其他任何地方(即不同的前任)，那么可以得出结论，后继值应该与前一个值保持连接。当发生这种情况时，将测试下一个后继者以查看是否可以形成完整的三元组，...等。

在下面的代码中，我使用了与问题中提供的不同的输入数据，因为与其他解决方案(在我之前发布的)为其生成的结果相比，此解决方案为其生成不同的输出。

代码使用ES6语法:

var input = [
  [1,3],
  [9,11,7,12,2],
  [5,0,7,12,2,8,10,7,12,2],
  [1]
];

// build hash (map)
var hash = input.reduce ( (hash, arr) => 
    arr.reduce ( (hash, val, index) => 
        // Collect the array element's references in a Map keyed by value: 
        hash.set(val, (hash.get(val) || []).concat({ arr, index })),
        hash 
    ), new Map() // initial value of the hash is an empty Map
);

var result = Array.from(hash, ([val, matches]) => {
    var match = matches[0];
    // Compare the sucessors of the elements that are equal
    for (var offset = 1; match.index + offset < match.arr.length; offset++) {
        var valAtOffset = match.arr[match.index+offset];
        // If the sucessor values only occur as successor of the preceding value, 
        // and all these successors have the same value, then keep this value together
        // with the preceding value:
        if (hash.get(valAtOffset).length !== matches.length ||
            matches.some( match => match.arr[match.index+offset] !== valAtOffset )) break;
        // Remove the hash entry for the value that is now part of this unbroken sequence
        hash.delete(valAtOffset);
    }
    return match.arr.slice(match.index, match.index+offset);
});

// output:
console.log(JSON.stringify(result));