array = [[1, 2], [13, 14], [4, 5], [80, 30], [12, 14], [10, 90], [3, 2], [6, 9], [1, 5], [4, 5], [5, 9], [4, 3], [13, 12]]
//expected
output = [[1, 2], [13, 14], [4, 5], [80, 30], [10, 90], [3, 2], [6, 9], [4, 5], [5, 9], [4, 3], [13, 12]]
You can consider the subarrays as lines, for example, [1,2] would be a line connected from point 1 to point 2. Therefore, [1,2],[3,2],[4,3],[4,5],[4,3] would correlate with several short lines that connect point 1 to point 5, because there is a line connected from point 1 to 2, 2 to 3, 3 to 4, and 4 to 5.
If the array contains a larger single line that is point 1 to point 5, it should be filtered out. This is to remove all longer lines that already have their points defined in more shorter lines. What algorithm could be used to solve this?
I have tried the code below at https://codepen.io/Maximusssssu/pen/jOYXrNd?editors=0012
The first part outputs all subarrays in ascending order for readability, whereas for the second part, I have tried the include() method to check whether a node is present in the subarray, and get its position.
array = [[1, 2], [13, 14], [4, 5], [80, 30], [12, 14], [10, 90], [3, 2], [6, 9], [1, 5], [4, 5], [5, 9], [4, 3], [13, 12]]
array_ascending_arr = [];
for (let i = 0; i < array.length; i++) {
let subarrayy = array[i].sort(function(a, b) {
return a - b
});
array_ascending_arr.push(subarrayy);
}
console.log(array_ascending_arr) // output all subarrays in ascending order back into array
for (let k = 1; k < 5; k++) {
for (let m = 0; m < array.length; m++) {
for (let i = 1; i < 2; i++) {
if (array_ascending_arr[m].includes(k) == true) {
console.log(m)
}
}
}
console.log(".......")
}You could try for an adjacency list. My understanding of the algorithm is if two pairs share an edge they will combine to form a new edge until all sets are unique.
the main idea is to calculate the difference in number of intermediate elements and not in value
if we have [[1,2],[14,10],[4,6],[9,2] that makes a sequence = [1,2,4,6,9,10,14] (sorted)
return delta values:
[1,2] -> d:1
[9,2] -> d:3 // the 9 is three positions away from the 2
the principle is therefore to process starting from the least distant values towards those most distant
(the other sorting criteria are secondary and are mainly useful for debugging)
note: duplicate pairs are also eliminated
const
test1 = [[1,2],[13,14],[4,5],[80,30],[12,14],[10,90],[3,2],[6,9],[1,5],[4,5],[5,9],[4,3],[13,12]]
, test2 = [[1,2],[4,5],[30,80],[12,18],[10,90],[2,3],[6,9],[1,5],[4,6],[5,9],[3,4],[12,13],[12,14],[14,15],[15,18]]
;
console.log('test1:\n', JSON.stringify( combination( test1 )))
console.log('test2:\n', JSON.stringify( combination( test2 )))
function combination(arr)
{
let
nodes = arr.flat().sort((a,b)=>a-b).filter((c,i,{[i-1]:p})=>(c!==p))
, sets = nodes.map(g=>[g])
, bads = []
;
arr // i:index, s:start(min), e:end(max), d: delta
.map(([v0,v1],i) => ({i,s:Math.min(v0,v1),e:Math.max(v0,v1), d:Math.abs(nodes.indexOf(v0) - nodes.indexOf(v1))}))
.sort((a,b) => (a.d-b.d) || (a.s-b.s) || (a.e-b.e) || (a.i-b.i) )
.forEach(({i,s,e,d}) =>
{
let
gS = sets.find(n=>n.includes(s))
, gE = sets.find(n=>n.includes(e))
;
if (gS === gE) { bads.push(i) }
else { gS.push(...gE); gE.length=0 }
})
//console.log( sets.filter(a=>a.length).map(a=>JSON.stringify(a)).join(' - ') )
return arr.filter((x,i)=>!bads.includes(i))
}.as-console-wrapper { max-height: 100% !important; top: 0; }
.as-console-row::after { display: none !important; }So from what I understand, you're trying to remove any set of numbers that encompasses a range greater than any that are smaller. The following code should do this:
array.filter(pair => {
// Get the smaller and larger numbers from the pair
const [small, big] = pair.sort((a,b) => a-b)
// Check if this pair is larger than any others
return !array.some(test => {
const [testSmall, testBig] = test.sort((a,b) => a-b)
return big > testBig && small < testSmall
})
})
Note that this won't remove duplicates.
If you don't mind your subarrays being reordered in the final array, you can simplify it a bit by sorting them all at the beginning:
array
.map(pair => pair.sort((a,b) => a-b))
.filter(([s, b], _, arr) => !arr.some(([ts, tb]) => b>tb && s<ts))