Tengo una gran variedad de subconjuntos. Cada submatriz tiene al menos un elemento que está duplicado al menos en una submatriz más. Por ejemplo:

[
    ['aaa', 'bbb', 'ccc'],
    ['ddd', 'aaa'],
    ['aaa', 'bbb', 'ccc', 'eee'],
    ['kkk', 'mmm', 'nnn'],
    ['mmm', 'ooo']
]

En este caso, 'ddd' y 'eee' no se duplican en ninguna parte, pero otros elementos en las mismas subcadenas se duplican al menos en una submatriz más. Necesito agrupar elementos en nuevas submatrices para recibir el siguiente resultado:

[
    ['aaa', 'bbb', 'ccc', 'ddd', 'eee'],
    ['kkk', 'mmm', 'nnn', 'ooo']
]

En otras palabras, necesito agrupar "amigos". Entonces, si 'ddd' es un "amigo" en algún lugar para 'aaa' y si 'eee' es un amigo en algún lugar para 'bbb' y 'aaa' y 'bbb' también son amigos, los agrupamos a todos en una nueva subcadena. Pero 'mmm' no es un amigo para 'aaa', 'bbb', etc., pero es un amigo para kkk y nnn y ooo, así que agrúpelos en otra subcadena

1
stckvrw 29 oct. 2019 a las 16:44

3 respuestas

La mejor respuesta

Primero puede usar reduce y Set para obtener una matriz de valores únicos y luego map para una matriz de matrices con valores únicos.

const data = [
  ['aaa', 'bbb', 'ccc'],
  ['ddd', 'aaa'],
  ['aaa', 'bbb', 'ccc', 'eee'],
  ['kkk', 'mmm', 'nnn'],
  ['mmm', 'ooo']
]

const result = data.reduce((r, e) => {
  const match = r.find(a => e.some(s => a.has(s)))
  if (!match) r.push(new Set(e));
  else e.forEach(el => match.add(el))
  return r
}, []).map(e => Array.from(e))

console.log(result)
5
Nenad Vracar 29 oct. 2019 a las 13:54

Una solución diferente, donde el orden no importa.

Además de las soluciones dadas, y la falta de unirse a grupos con elementos que crean primero un grupo temporal y la matriz de elementos pertenece a dos grupos, como

var data = [
        ['aaa', 'bbb', 'ccc'], // group aaa, bbb, ccc
        // ...
        ['x', 'y'],            // creates own group x, y
        ['x', 'aaa']           // fails here to join x, y with aaa, ...
    ],

con estos datos se realiza una verificación y los grupos se unen a un solo grupo, así como a sus elementos.

Esta solución toma una tabla hash con los elementos como claves y un objeto que contiene una sola propiedad con un Set.

{ s: new Set }

Esto es necesario para usar la referencia de objeto para el mismo grupo y la referencia del conjunto para el mismo grupo, pero no para los elementos que no están en la matriz real.

Si más tarde se encuentra una propiedad de la tabla hahs y no es igual al grupo real, o el conjunto no es igual al conjunto del grupo, entonces todos los elementos obtienen el mismo conjunto y todos los hashes del grupo se reasignan al conjunto de grupos.

Al final, los valores se toman de la tabla hash, solo la propiedad set se usa para obtener conjuntos únicos y los conjuntos se convierten en matrices.

Voilà.

var data = [['aaa', 'bbb', 'ccc'], ['ddd', 'aaa'], ['aaa', 'bbb', 'ccc', 'eee'], ['kkk', 'mmm', 'nnn'], ['mmm', 'ooo'],['x', 'y'], ['x', 'aaa']],
    hash = data.reduce((r, a) => {
        var common = { s: new Set };
        a.forEach(v => {
            common.s.add(v);
            if (!r[v]) return r[v] = common;
            if (r[v] === common || r[v].s === common.s) return;
            common.s.forEach(k => {
                r[k].s = r[v].s;
                r[v].s.add(k);
            });
            common.s = r[v].s;
        });
        return r;
    }, {}),
    grouped = Array
        .from(new Set(Object.values(hash).map(({ s }) => s)))
        .map(s => Array.from(s));

console.log(grouped);
.as-console-wrapper { max-height: 100% !important; top: 0; }

Un enfoque diferente utilizando solo una matriz de conjuntos y filtrando la matriz para los elementos encontrados o agregando los valores de una matriz en un nuevo conjunto.

function getGroups(array) {
    var groups = [],
        once;

    do {
        once = false;
        array = array.filter(a => {
            var temp;
            if (a.some(v => temp = groups.find(s => s.has(v)))) {
                a.forEach(Set.prototype.add, temp);
                return false;
            }
            if (once) return true;
            groups.push(new Set(a));
            once = true;
        });
    } while (array.length);
    return groups.map(s => Array.from(s));
}

var data = [['aaa', 'bbb', 'ccc'], ['ddd', 'aaa'], ['aaa', 'bbb', 'ccc', 'eee'], ['kkk', 'mmm', 'nnn'], ['mmm', 'ooo'], ['x', 'y'], ['x', 'aaa']],
    result = getGroups(data);

console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }
1
Nina Scholz 1 nov. 2019 a las 11:40

Puedes usar Establecer y reducir

  • Recorra el conjunto, use el valor de unión actual para usarlo como clave
  • Compruebe si alguno de los elementos de la matriz actual ya está presente en op o no
  • Si ya está presente, agregue la matriz actual al conjunto existente, de lo contrario, establezca una nueva clave con el valor como matriz actual como conjunto
let data = [['aaa', 'bbb', 'ccc'],['ddd', 'aaa'], ['aaa', 'bbb', 'ccc', 'eee'],['kkk', 'mmm', 'nnn'],['mmm', 'ooo']]

let final = data.reduce((op, inp) => {
  let key = inp.join(',')
  let included = Object.keys(op)
  let found = included.find(v => inp.some(curr => v.includes(curr)))
  if (found) {
    op[found] = new Set([...op[found], ...inp])
  } else {
    op[key] = new Set(inp)
  }
  return op
}, {})

console.log(Object.values(final).map(v => [...v]))
2
Code Maniac 29 oct. 2019 a las 13:56