我有一组形式的数组
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 中这样做。我认为部分原因是我未能掌握的逻辑问题。我
现实世界的用例是合并路径名称,以便规范分类层次结构,该分类层次结构包含许多项目,其中混合了完整路径和 chop 路径,例如/Science/Biology 和/Biology 标准化为/Science/Biology
非常感谢您提供有关如何执行此操作的任何指示。
最佳答案
首先用 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; }
关于javascript - 将超集数组叠加到顺序/顺序很重要的子集数组上(在 Javascript 中),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25234939/