How to resolve the algorithm Order disjoint list items step by step in the JavaScript programming language
How to resolve the algorithm Order disjoint list items step by step in the JavaScript programming language
Table of Contents
Problem Statement
Given M as a list of items and another list N of items chosen from M, create M' as a list with the first occurrences of items from N sorted to be in one of the set of indices of their original occurrence in M but in the order given by their order in N. That is, items in N are taken from M without replacement, then the corresponding positions in M' are filled by successive items from N.
The words not in N are left in their original positions.
If there are duplications then only the first instances in M up to as many as are mentioned in N are potentially re-ordered.
Is ordered as:
Show the output, here, for at least the following inputs:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Order disjoint list items step by step in the JavaScript programming language
The provided code is a JavaScript function that performs the "disjoint order" operation on two lists of strings. The disjoint order of two lists is a new list that contains the elements of the first list followed by the elements of the second list, with the caveat that any elements that appear in both lists are only included once, and their position in the result is determined by their position in the first list.
The code uses a recursive function called segments to divide the second list into segments, where each segment consists of consecutive elements that are also present in the first list. The disjointOrder function then uses these segments to construct the result.
Here is a breakdown of the code:
- The
disjointOrderfunction takes two lists of strings as input and returns a new list of strings. - The
segmentsfunction takes two lists of strings as input and returns a list of segments. Each segment is a list of strings that are consecutive in the second list and also appear in the first list. - The
disjointOrderfunction uses the segments to construct the result by iterating over the segments and adding the elements of each segment to the result. If an element appears in multiple segments, it is only included once in the result. - The
mainfunction tests thedisjointOrderfunction with a variety of input lists and prints the results.
Here is an example of how to use the disjointOrder function:
const M = "the cat sat on the mat";
const N = "mat cat";
const result = disjointOrder(words(M))(words(N));
console.log(result); // ["the", "cat", "sat", "on", "the", "mat", "mat", "cat"]
In this example, the disjointOrder function is used to combine the two lists of words, M and N. The result is a new list of words that contains all of the words from both lists, with the caveat that any words that appear in both lists are only included once, and their position in the result is determined by their position in the first list.
Source code in the javascript programming language
(() => {
"use strict";
// ------------ ORDER DISJOINT LIST ITEMS ------------
// disjointOrder :: [String] -> [String] -> [String]
const disjointOrder = ms =>
ns => zipWith(
a => b => [...a, b]
)(
segments(ms)(ns)
)(
ns.concat("")
)
.flat();
// segments :: [String] -> [String] -> [String]
const segments = ms =>
ns => {
const dct = ms.reduce((a, x) => {
const
wds = a.words,
found = wds.indexOf(x) !== -1;
return {
parts: [
...a.parts,
...(found ? [a.current] : [])
],
current: found ? [] : [...a.current, x],
words: found ? deleteFirst(x)(wds) : wds
};
}, {
words: ns,
parts: [],
current: []
});
return [...dct.parts, dct.current];
};
// ---------------------- TEST -----------------------
const main = () =>
transpose(transpose([{
M: "the cat sat on the mat",
N: "mat cat"
}, {
M: "the cat sat on the mat",
N: "cat mat"
}, {
M: "A B C A B C A B C",
N: "C A C A"
}, {
M: "A B C A B D A B E",
N: "E A D A"
}, {
M: "A B",
N: "B"
}, {
M: "A B",
N: "B A"
}, {
M: "A B B A",
N: "B A"
}].map(dct => [
dct.M, dct.N,
unwords(
disjointOrder(
words(dct.M)
)(
words(dct.N)
)
)
]))
.map(col => {
const
w = maximumBy(
comparing(x => x.length)
)(col).length;
return col.map(justifyLeft(w)(" "));
}))
.map(
([a, b, c]) => `${a} -> ${b} -> ${c}`
)
.join("\n");
// ---------------- GENERIC FUNCTIONS ----------------
// comparing :: (a -> b) -> (a -> a -> Ordering)
const comparing = f =>
// The ordering of f(x) and f(y) as a value
// drawn from {-1, 0, 1}, representing {LT, EQ, GT}.
x => y => {
const
a = f(x),
b = f(y);
return a < b ? -1 : (a > b ? 1 : 0);
};
// deleteFirst :: a -> [a] -> [a]
const deleteFirst = x => {
const go = xs => Boolean(xs.length) ? (
x === xs[0] ? (
xs.slice(1)
) : [xs[0]].concat(go(xs.slice(1)))
) : [];
return go;
};
// unwords :: [String] -> String
const unwords = xs =>
// A space-separated string derived
// from a list of words.
xs.join(" ");
// words :: String -> [String]
const words = s =>
// List of space-delimited sub-strings.
s.split(/\s+/u);
// zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
const zipWith = f =>
// A list constructed by zipping with a
// custom function, rather than with the
// default tuple constructor.
xs => ys => xs.map(
(x, i) => f(x)(ys[i])
).slice(
0, Math.min(xs.length, ys.length)
);
// ---------------- FORMATTING OUTPUT ----------------
// justifyLeft :: Int -> Char -> String -> String
const justifyLeft = n =>
// The string s, followed by enough padding (with
// the character c) to reach the string length n.
c => s => n > s.length ? (
s.padEnd(n, c)
) : s;
// maximumBy :: (a -> a -> Ordering) -> [a] -> a
const maximumBy = f =>
xs => Boolean(xs.length) ? (
xs.slice(1).reduce(
(a, x) => 0 < f(x)(a) ? (
x
) : a,
xs[0]
)
) : undefined;
// transpose :: [[a]] -> [[a]]
const transpose = rows =>
// The columns of a matrix of consistent row length,
// transposed into corresponding rows.
Boolean(rows.length) ? rows[0].map(
(_, i) => rows.flatMap(
v => v[i]
)
) : [];
// MAIN ---
return main();
})();
You may also check:How to resolve the algorithm Palindrome detection step by step in the Go programming language
You may also check:How to resolve the algorithm Find limit of recursion step by step in the BQN programming language
You may also check:How to resolve the algorithm Letter frequency step by step in the SenseTalk programming language
You may also check:How to resolve the algorithm Sort disjoint sublist step by step in the Wren programming language
You may also check:How to resolve the algorithm Multifactorial step by step in the C++ programming language