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]] Puede considerar los subarreglos como líneas, por ejemplo, [1,2] sería una línea conectada desde el punto 1 al punto 2. Por lo tanto, [1,2],[3,2],[4,3],[4,5],[4,3] se correlacionaría con varias líneas cortas que conectan el punto 1 con el punto 5, porque hay una línea conectada del punto 1 al 2, del 2 al 3, del 3 al 4 y del 4 al 5.
Si la matriz contiene una sola línea más grande que es del punto 1 al punto 5, debe filtrarse. Esto es para eliminar todas las líneas más largas que ya tienen sus puntos definidos en líneas más cortas. ¿Qué algoritmo podría usarse para resolver esto?
Probé el siguiente código en https://codepen.io/Maximusssssu/pen/jOYXrNd?editors=0012
La primera parte genera todos los subarreglos en orden ascendente para facilitar la lectura, mientras que para la segunda parte, probé el método include() para verificar si un nodo está presente en el subarreglo y obtener su posición.
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(".......") }Podría intentar una lista de adyacencia. Mi comprensión del algoritmo es que si dos pares comparten una ventaja, se combinarán para formar una nueva ventaja hasta que todos los conjuntos sean únicos.
la idea principal es calcular la diferencia en número de elementos intermedios y no en valor
si tenemos [[1,2],[14,10],[4,6],[9,2] que hace una secuencia = [1,2,4,6,9,10,14] (ordenada)
devolver valores delta:
[1,2] -> d:1 [9,2] -> d:3 // the 9 is three positions away from the 2 por lo tanto, el principio es procesar a partir de los valores menos distantes hacia los más distantes
(los otros criterios de clasificación son secundarios y son principalmente útiles para la depuración)
nota: los pares duplicados también se eliminan
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)=>ab).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) => (ad-bd) || (as-bs) || (ae-be) || (ai-bi) ) .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; }Entonces, por lo que entiendo, está tratando de eliminar cualquier conjunto de números que abarque un rango mayor que cualquiera que sea más pequeño. El siguiente código debería hacer esto:
array.filter(pair => { // Get the smaller and larger numbers from the pair const [small, big] = pair.sort((a,b) => ab) // Check if this pair is larger than any others return !array.some(test => { const [testSmall, testBig] = test.sort((a,b) => ab) return big > testBig && small < testSmall }) })Tenga en cuenta que esto no eliminará los duplicados.
Si no le importa que sus subarreglos se reordenen en el arreglo final, puede simplificarlo un poco ordenándolos todos al principio:
array .map(pair => pair.sort((a,b) => ab)) .filter(([s, b], _, arr) => !arr.some(([ts, tb]) => b>tb && s<ts))