将超集数组覆盖到重要的子集数组上(在Javascript中)

Question

我有一组表单数组

A= [1,2,3,4,5,6]
B= [7,8,9]
C= [5,6]
D= [9]

我希望在子集(子序列)上“覆盖”右侧(后缀)超集(严格地说，超级序列)，以便结果集看起来如下：

A= [1,2,3,4,5,6] (unchanged, because not a subset of anything)
B= [7,8,9] (unchanged, because not a subset of anything)
C= [1,2,3,4,5,6] (C overlayed with A, because C is a subset of A)
D= [7,8,9] (D overlayed with B, because D is a subset of B)

我在node.js做这件事。我认为这在一定程度上是我未能理解的一个逻辑问题。我

现实世界中的用例正在合并路径名，以便规范化一个分类层次结构，其中包含多个项目，其中包含完整路径和截断路径，例如/Science/生物学和/Biology被标准化为/Science/生物学。

非常感谢你对如何做到这一点的指点。

Answer 1

先用Haskell写了这个，只是为了把算法写下来。

import Data.List (maximumBy, tails)
import Data.Map (Map, findWithDefault)
import qualified Data.Map.Strict as Map
import Data.Ord (comparing)

main :: IO()
main = putStrLn $ show $ normalize [[1..6], [7..9], [5..6], [9]]

normalize :: Ord a => [[a]] -> [[a]]
normalize xxs = map (\xs -> findWithDefault xs xs index) xxs
  where index = suffixIndex xxs

suffixIndex :: Ord a => [[a]] -> Map [a] [a]
suffixIndex xxs = Map.fromListWith (maxBy length) entries
  where entries = [ (suf, xs) | xs <- xxs, suf <- suffixes xs ]
        suffixes xs = drop 1 $ filter (not . null) $ tails xs

maxBy :: Ord b => (a -> b) -> a -> a -> a
maxBy f x y = maximumBy (comparing f) [x, y]

suffixIndex将每个后缀映射到具有该后缀的最长列表。因此，例如，[[1,2,3], [2,3]]会产生一个类似于[2,3] -> [1,2,3], [3] -> [1,2,3]的索引。

一旦建立了索引，通过应用映射(如果存在映射)，每个列表就会被“规范化”(使用您的单词)。

现在在Javascript里。

console.log(JSON.stringify(normalize([[1,2,3,4,5,6], [7,8,9], [5,6], [9]])));

function normalize(xxs) {
    var index = suffixIndex(xxs);
    return xxs.map(function (xs) {
        str = JSON.stringify(xs);
        return index.hasOwnProperty(str) ? index[str] : xs;
    });
}

function suffixIndex(xxs) {
    var index = {};
    xxs.forEach(function (xs) {
        suffixes(xs).forEach(function (suffix) {
            var str = JSON.stringify(suffix);
            index[str] = index.hasOwnProperty(str)
                ? maxBy(lengthOf, index[str], xs)
                : xs;
        });
    });
    return index;
}

function suffixes(xs) {
    var i, result = [];
    for (i = 1; i < xs.length; i++) result.push(xs.slice(i));
    return result;
}

function lengthOf(arr) { return arr.length; }

function maxBy(f, x, y) { return f(x) > f(y) ? x : y; }

Answer 2

也许这并不是最优雅的方法，但是比较字符串化的版本是可行的。假设数组中有A、B、C和D

function overlay (arr) {
  arr = arr.map(function(item) {
    // Stringify the item
    var itemStr = item.join(",");
    // Loop through each item in the array
    arr.forEach(function(compare) {
      // Stringify the item to compare
      var compareStr = compare.join(",");
      // If we're not comparing it to itself, and the rightmost part
      // of the comparison string == the item in question, set the
      // item to the value of "compare"
      if (compareStr != itemStr && 
          compare.join(",").substr(0 - itemStr.length) == itemStr) {
        item = compare;
      }
    });
    return item;
  });
}

您可以通过对数组中的所有项进行预调整版本来进行优化。