将一个超集数组覆盖到一个子数组，其中order / sequence很重要（在Javascript中）
我有一组forms的数组
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中做这个 我想部分是这个逻辑问题，我没有把握。 一世
现实世界的用例是合并path名称，以规范一个分类层次结构，这个分类层次结构有很多项目，包括完整path和截断path，例如/科学/生物学和/生物学被归一化到/科学/生物学
非常感谢指导如何做到这一点。
首先在Haskell中编写这个函数就是为了减lessalgorithm。
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 fxy = maximumBy (comparing f) [x, y]
suffixIndex将每个后缀映射到具有该后缀的最长列表。 因此，例如[[1,2,3], [2,3]]产生一个类似于[2,3] -> [1,2,3], [3] -> [1,2,3] 。
一旦build立索引，每个列表都是“标准化的”（用你的单词），只要应用地图（如果存在映射）。
现在在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; }
可能不是最优雅的方式来做，但比较string版本将工作。 假设你有一个数组arr中的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; }); }
您可以通过对数组中所有项目进行预串联处理来进行优化。