Aquí hay algunas matrices de valores:
values = [
[1,2,3],
[2,3,4],
[8,9,10],
[9,10,11],
[13,14,15]
];
Quiero crear nuevos arreglos ordenados numéricamente a partir de la unión de los valores de los arreglos cuando hay una intersección de los valores de dos o más arreglos.
Los valores en estas nuevas matrices ordenadas serán únicos.
Si una matriz no intersecta ninguna otra matriz, entonces incluimos esa matriz en los resultados (por ejemplo, [13,14,15] en el ejemplo).
Por ejemplo:
clusters = [
[1,2,3,4],
[8,9,10,11],
[13,14,15]
];
Dado que el valor[0] y el valor[1] se cruzan, agregamos una unión de sus valores a los grupos.
Dado que el valor [2] y el valor [3] se cruzan, agregamos una unión de sus valores a los grupos.
Dado que el valor[4] no intersecta el valor[0] con el valor[4], simplemente agregamos valor[5] a los clústeres.
Ahora, si hubiera un valor[6] = [3, 100], entonces nuestros clusters se verían así:
clusters = [
[1,2,3,4,100],
[8,9,10,11],
[13,14,15]
];
debido a que el valor[6] intersecciona el valor[0] y el valor[1], entonces sumamos a su unión.
¿Existe alguna técnica o forma óptima de hacer esto?
En mi ejemplo, las matrices originales están ordenadas, pero puede que ese no sea necesariamente el caso.
¿Es [2, 3, 4, 1] un resultado aceptable para los grupos [0]?
- Sebastián Simón
26/03/2021 a las 22:57
Los clusters de @SebastianSimon deben ordenarse, aclararé el OP
- jedierikb
26/03/2021 a las 23:00
¿Qué pasa si dos matrices contienen [2, 1] y [1, 3]? ¿La matriz fusionada debería ser [2, 1, 3] o [1, 2, 3]? ¿“Ordenado” en términos de clasificación numérica o según las matrices originales?
- Sebastián Simón
26/03/2021 a las 23:04
@SebastianSimonordenación numérica de los valores, entonces [1,2,3]
- jedierikb
26/03/2021 a las 23:16
Casi tengo un algoritmo O (n log n) funcional (un solo paso por todos los elementos y una clasificación posterior), pero no produce un resultado final en casos como [ [ 1, 2 ], [ 3, 4 ], [ 2, 3 ] ]: Array.from(new Set(values.reduce((r, a) => { a.forEach((e) => { if(r.has(a)){ r.get(a).push(e); } else if(r.has(e)){ r.set(a, r.get(e)).get(e).push(e); } else { r.set(e, a); } }); return r; }, nuevo Mapa()).values()), (a) => Array.from(nuevo Conjunto(a)).sort(( a, b) => a - b));.
- Sebastián Simón
27 de marzo de 2021 a las 0:35
------------------------------------
Aquí hay un fragmento editado en respuesta a los comentarios usando .reduceRight(), sembrando el acumulador con una copia de la matriz pasada y aún usando some() e include() para encontrar duplicados.
reduceRight() itera la matriz a la inversa, mientras que findIndex() busca desde el principio. Cuando se encuentra una coincidencia, la matriz iterada actual se envía a la matriz coincidente y luego el elemento actual se elimina del acumulador usando splice().
function clusterDuplicates(arr) {
return arr
.reduceRight((a, arr, i) => {
if (i) {
let j = a.slice(0, i).findIndex(_arr => arr.some(x => _arr.includes(x)));
if (~j) {
a[j].push(...arr);
a.splice(i, 1);
}
}
return a
}, [...arr])
.map(arr => [...new Set(arr)].sort((a, b) => a - b));
}
console.log(clusterDuplicates([[1, 2, 3], [3, 4, 2], [8, 9, 10], [9, 11, 10], [14, 13, 15]]));
console.log(clusterDuplicates([[1, 2], [3, 4], [2, 3]]));
.as-console-wrapper { max-height: 100% !important; top: 0; }
Respuesta original
Como se indicó en los comentarios, esto no busca duplicados.
Aquí hay unImplementación bastante concisa usando reduce() buscando intersecciones usando some() e include(). Luego, el resultado se asigna para eliminar duplicados usando Conjuntos y luego se ordena.
const
values = [[1, 2, 3], [3, 4, 2], [8, 9, 10], [9, 11, 10], [14, 13, 15]],
result =
values
.reduce((a, arr) => {
let i = a.findIndex(_arr => arr.some(x => _arr.includes(x)));
if (i === -1) {
i = a.push([]) - 1;
}
a[i].push(...arr);
return a
}, [])
.map(arr => [...new Set(arr)].sort((a, b) => a - b));
console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }
0
------------------------------------
Para ver si dos matrices se cruzan, una forma sencilla y agradable es comparar el tamaño del conjunto de ambas matrices juntas, con el tamaño establecido de cada matriz, y si son diferentes, sabemos que se cruzan.
A continuación se muestra un ejemplo...
const values = [
[1,2,3],
[8,9,10],
[2,3,4],
[9,10,11],
[13,14,15]
];
function arrayItersect(a,b) {
return new Set([...a,...b]).size !==
new Set(a).size + new Set(b).size;
}
function joinIntersections(v) {
const a = [...v]; //make a copy
for (let l = 0; l < a.length-1; l += 1) {
let l2 = l + 1;
while (l2 < a.length) {
if (arrayItersect(a[l], a[l2])) {
a[l] =
[...new Set(
[...a[l],...a.splice(l2, 1)[0]]
)];
} else l2 ++;
}
}
return a;
}
console.log(joinIntersections(values));
6
@SebastianSimon Sí, no estoy 100% seguro de lo que el OP significa por intersección aquí. Mirando más de cerca la salida, asumo que el OP significa mantener juntos los valores consecutivos. He actualizado para hacer esto en su lugar.
- Keith
26/03/2021 a las 23:28
disculpas, he actualizado el OP para aclarar
- jedierikb
26/03/2021 a las 23:54
@jedierikb Ah, claro, eso ahora tiene sentido... He actualizado mi respuesta...
- Keith
27 de marzo de 2021 a las 0:25
@SebastianSimon Sí, podría optimizarse aquí, tomó la ruta fácil de simplemente iterar si se unen matrices. Si es probable que el conjunto de datos para esto sea grande, definitivamente consideraría optimizarlo.
- Keith
27 de marzo de 2021 a las 0:33
1
El mismo problema aquí: [ [ 1, 2 ], [ 3, 4 ], [ 2, 3 ] ] se está dividiendo en [ [ 1, 2, 3 ], [ 3, 4 ] ], pero llamándolo de otro modo el tiempo en el resultado lo fusiona con el esperado [ [ 1, 2, 3, 4 ] ].
- Sebastián Simón
27/03/2021 a las 13:08
------------------------------------
Utilice el bucle for y para cada submatriz verifique con la matriz anterior (última) si tiene intersección. Si es una intersección, agregue la matriz fusionada al resultado.
values = [
[1, 2, 3],
[2, 3, 4],
[8, 9, 10],
[9, 10, 11],
[13, 14, 15],
];
const intersect = (arr1, arr2) => {
const both = [...arr1, ...arr2];
const uniq = [...new Set(both)];
return uniq.length !== both.length ? uniq : null;
};
const compact = (arrArr) => {
if (arrArr?.length < 2) {
return arrArr;
}
const res = [];
let last = arrArr[0];
for (let i = 1; i < arrArr.length; i++) {
last = intersect(last, arrArr[i]) ?? (res.push(last), arrArr[i]);
}
res.push(last);
return res;
};
console.log(compact(values))
