I have a set of arrays of the form
A= [1,2,3,4,5,6]
B= [7,8,9]
C= [5,6]
D= [9]
I want to "overlay" the right-sided (suffix) supersets (strictly speaking, super-sequences) on the subsets (subsequences) so that the result set looks like this:
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)
I'm doing this in node.js. I think partly it is a logic problem that I'm failing to grasp. I
The real-world use case is merging path names in order to normalize a classification hierarchy that has many items with a mixture of full and truncated paths, e.g. /Science/Biology and /Biology gets normalized to /Science/Biology
Many thanks for any pointers to how to do this.
Probably not the most elegant way to do it, but comparing stringified versions will work. Assuming you have A, B, C and D in an array arr:
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;
});
}
You could optimize by making a pre-stringified version of all the items in the array.
Wrote this in Haskell first just to get the algorithm down.
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 maps each suffix to the longest list having that suffix. So, for example [[1,2,3], [2,3]] results in an index that looks like [2,3] -> [1,2,3], [3] -> [1,2,3].
Once the index is built, each list is "normalized" (to use your word) by just applying the map (if a mapping exists).
And now in 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; }