Le type de données json (simplifié) suivant définit un contact:

{
  id:   number;
  name: string;
  phone: string;
  email: string
}

Il existe le groupe de données suivant:

+---+----------+-------------+---------------------------+ 
|id | name     | phone       |email                      | 
+---+----------+-------------+---------------------------+
|1  | John     | 11111111    |aaaa@test.com              | 
|2  | Marc     | 22222222    |bbbb@test.com              | 
|3  | Ron      | 99999999    |aaaa@test.com              |
|4  | Andrew   | 55555555    |dddd@test.com              |
|5  | Wim      | 99999999    |gggg@test.com              |
|6  | Marc     | 33333333    |cccc@test.com              |
|7  | Dan      | 44444444    |cccc@test.com              |
+---+----------+-------------+---------------------------+

Le but est de trouver les groupes qui appartiennent ensemble en utilisant javascript (éventuellement dans lodash, mais l'idée principale est de clarifier l'algorithme) selon la contrainte suivante: un contact appartient à un groupe lorsque l'un des critères suivants est le même: nom, Téléphone ou email. Les résultats montrent les identifiants regroupés sous forme de tableaux dans les tableaux. un contact dans un groupe de 1 est ignoré.

Dans l'exemple ci-dessus, cela signifie que les contacts avec les identifiants 1,3,5 appartiennent ensemble car 1,3 partagent le même e-mail et 3 et 5 partagent le même numéro de téléphone. De même, 2,6,7: 2 et 6 ont le même nom et 6 et 7 ont le même e-mail. 5 n'a rien en commun. Le résultat attendu est donc:
[[1,3,5], [2,6,7]]

Contexte: Une solution qui fonctionne est d'itérer sur chaque élément et de vérifier le reste de la liste si le nom, l'adresse e-mail ou le téléphone est le même. Si c'est le cas, regroupez-les et retirez-les de la liste (dans l'exemple, nous comparons 1 à tous les éléments de la liste et seulement 3 sont trouvés). Le problème est que les éléments suivants doivent également être vérifiés à nouveau dans ces groupes, car dans ce cas, 5 n'est pas encore détecté comme faisant partie du groupe. Cela rend l'algorithme complexe, alors que je soupçonne qu'il existe un moyen simple de résoudre ce problème en temps linéaire. Il pourrait également y avoir un nom pour cette classe de problèmes? "

10
Han 20 nov. 2018 à 12:18

4 réponses

Meilleure réponse

Idée:

  • Commencez avec 0 groupes
  • Itérer votre liste de contacts
  • Vérifiez s'il existe un groupe avec le nom du contact, le téléphone ou l'e-mail. Fusionnez tous les membres de ces groupes dans le même groupe. Ajoutez-vous ensuite à ce groupe. Sinon, commencez un nouveau groupe avec vous-même et définissez le nom, le téléphone et le groupe de messagerie comme vous-même.

Union find est une structure efficace pour gérer la fusion des ensembles disjoints. Code extrait de ici. Comme il utilise la compression de chemin et l'union par rang, vous pouvez considérer que le code entier est linéaire dans la quantité de contacts.

var data = [
      {id:1,name:'John',phone:'11111111',email:'aaaa@test.com'},
      {id:2,name:'Marc',phone:'99999999',email:'bbbb@test.com'},
      {id:3,name:'Ron',phone:'99999999',email:'aaaa@test.com'},
      {id:4,name:'Andrew',phone:'55555555',email:'dddd@test.com'},
      {id:5,name:'Wim',phone:'99999999',email:'gggg@test.com'},
      {id:6,name:'Marc',phone:'33333333',email:'cccc@test.com'},
      {id:7,name:'Dan',phone:'44444444',email:'cccc@test.com'}
];

// UNION-FIND structure, with path comression and union by rank

var UNIONFIND = (function () {
    
    function _find(n)
    {
        if(n.parent == n) return n;	
        n.parent = _find(n.parent);	
        return n.parent;
    }
    
    return {
        makeset:function(id){    
            var newnode = {
                parent: null,
                id: id,
                rank: 0
            };
            newnode.parent = newnode;            
            return newnode;
        },
    
        find: _find,
     
        combine: function(n1, n2) {                                    
            var n1 = _find(n1);
            var n2 = _find(n2);
            
            if (n1 == n2) return;
        
            if(n1.rank < n2.rank)
            {
                n2.parent = n2;
                return n2;
            }
            else if(n2.rank < n1.rank)
            {
                n2.parent = n1;
                return n1;
            }
            else
            {
                n2.parent = n1;
                n1.rank += 1;
                return n1;
            }
        }
    };
})();

var groupHash = {name: {}, phone: {}, email: {}}
var groupNodes = []

data.forEach(function(contact){
  var group = UNIONFIND.makeset(contact.id);
  var groups = new Set();
  ["name", "phone", "email"].forEach(function(attr){
    if (groupHash[attr].hasOwnProperty(contact[attr])) groups.add(groupHash[attr][contact[attr]])
  });
  
  groups = Array.from(groups);
  groups.push(group);
  groupNodes.push(group);
  
  for(var i = 1; i < groups.length; i++) {
    UNIONFIND.combine(groups[0], groups[i]);
  }  
  
  ["name", "phone", "email"].forEach(function(attr){
      groupHash[attr][contact[attr]] = groups[0];
  });
  
})

var contactsInGroup = {}


groupNodes.forEach(function(group){
    var groupId = UNIONFIND.find(group).id;
    
    if (contactsInGroup.hasOwnProperty(groupId) == false) {
      contactsInGroup[groupId] = [];
    }
    
    contactsInGroup[groupId].push(group.id);
})

var result = Object.values(contactsInGroup).filter(function(list){
 return list.length > 1
})

console.log(result)
3
juvian 20 nov. 2018 à 14:59

Une façon d'accomplir ce dont vous avez besoin est de séparer les contacts en groupes. Chaque groupe contiendra une liste de names, phones et emails.

Ensuite, parcourez les contacts et voyez si le contact actuel appartient à l'un des groupes. Si ce n'est pas le cas, créez un nouveau groupe et définissez son names/phones/emails afin que les prochains contacts puissent tomber dans le même.

var data = [
      {id:1,name:'John',phone:'11111111',email:'aaaa@test.com'},
      {id:2,name:'Marc',phone:'22222222',email:'bbbb@test.com'},
      {id:3,name:'Ron',phone:'99999999',email:'aaaa@test.com'},
      {id:4,name:'Andrew',phone:'55555555',email:'dddd@test.com'},
      {id:5,name:'Wim',phone:'99999999',email:'gggg@test.com'},
      {id:6,name:'Marc',phone:'33333333',email:'cccc@test.com'},
      {id:7,name:'Dan',phone:'44444444',email:'cccc@test.com'}
];

var groups = [];

data.forEach(function(person){
  var phone = person.phone;
  var email = person.email;
  var name = person.name;
  var id = person.id;
  var found = false;
  groups.forEach(function(g){
    if(    g.names.indexOf(name) > -1 
        || g.phones.indexOf(phone)>-1 
        || g.emails.indexOf(email)>-1) {
      found = true;
      g.names.push(name);
      g.phones.push(phone);
      g.emails.push(email);
      g.people.push(id);
    }
  });
  if(!found) {
      groups.push({names:[name],phones:[phone],emails:[email],people:[id]});
  }
  
  
});
var output=[];
groups.forEach(function(g){
  output.push(g.people);
});
console.log(output);   //[ [1,3,5] , [2,6,7] , [4] ]
-1
Ahmad 20 nov. 2018 à 09:51

Voici une autre suggestion d'un itinéraire que vous pouvez emprunter. L'idée est d'utiliser un { {X0}} pour regrouper par id et conserver toutes les valeurs (vls) et les résultats combinés (ids) dans ce accumulator object.

De cette façon, vous pouvez facilement comparer les name/phone/email en utilisant Array.some + Array.includes (ce que fait la fonction getGroupId).

Une fois que vous avez groupé et obtenu le résultat presque final, il suffit de prettify le supprimer en supprimant les groupes avec length et en ne sélectionnant que le tableau ids du reste:

var data = [ {id:1,name:'John',phone:'11111111',email:'aaaa@test.com'}, {id:2,name:'Marc',phone:'22222222',email:'bbbb@test.com'}, {id:3,name:'Ron',phone:'99999999',email:'aaaa@test.com'}, {id:4,name:'Andrew',phone:'55555555',email:'dddd@test.com'}, {id:5,name:'Wim',phone:'99999999',email:'gggg@test.com'}, {id:6,name:'Marc',phone:'33333333',email:'cccc@test.com'}, {id:7,name:'Dan',phone:'44444444',email:'cccc@test.com'} ];

const getGroupId = (obj, vals) => Object.entries(obj)
   .find(([k,v]) => v.vls.some(x => vals.includes(x))) || []

const group = d => d.reduce((r, c) => {
   let values = Object.values(c), groupID = getGroupId(r, values)[0]
	
   if(!groupID)	
      r[c.id] = ({ vls: values, ids: [...r[c.id] || [], c.id] })
   else {
      r[groupID] = ({
         vls: [...r[groupID].vls, ...values], ids: [...r[groupID].ids, c.id]
      })
   }
   return r
}, {})

const prettify = grp => Object.values(grp).reduce((r,c) => {
   if(c.ids.length > 1)
     r.push(c.ids)
     return r
}, [])

console.log(prettify(group(data)))

Une chose à noter est que nous ne nous soucions pas du nombre de propriétés puisque nous faisons Object.values. Vous pouvez donc facilement ajouter un autre address ou fax à cette liste et cela fonctionnerait toujours avec zero code changes.

Selon les commentaires, voici une autre version qui fonctionne légèrement différemment:

var data = [ {id:1,name:'John',phone:'11111111',email:'aaaa@test.com'}, {id:2,name:'Marc',phone:'22222222',email:'bbbb@test.com'}, {id:3,name:'Ron',phone:'99999999',email:'aaaa@test.com'}, {id:4,name:'Andrew',phone:'55555555',email:'dddd@test.com'}, {id:5,name:'Wim',phone:'99999999',email:'gggg@test.com'}, {id:6,name:'Marc',phone:'33333333',email:'cccc@test.com'}, {id:7,name:'Dan',phone:'44444444',email:'cccc@test.com'} ];
var testData = [{ id: 1, name: 'John', phone: '1', email: 'a' }, { id: 2, name: 'Marc', phone: '2', email: 'b' }, { id: 3, name: 'Ron', phone: '1', email: 'b' }]; 

const getGroupId = (obj, vals) => Object.entries(obj)
  .find(([k,v]) => v.vls.some(x => vals.includes(x))) || []

const group = d => d.reduce((r,c,i,a) => {
  let values = Object.values(c), groupID = !i ? i : getGroupId(r, values)[0]

  if (!groupID) {		
    let hits = a.filter(x => 
       x.id != c.id && values.some(v => Object.values(x).includes(v)))
    hits.forEach(h => 
       r[c.id] = ({ vls: [...values, ...Object.values(h)], ids: [c.id, h.id] }))
  }
  else
    r[groupID] = r[groupID].ids.includes(c.id) ? r[groupID] : 
      ({ vls: [...r[groupID].vls, ...values], ids: [...r[groupID].ids, c.id] })      
  return r
}, {})

const prettify = grp => Object.values(grp).reduce((r, c) => {
  if (c.ids.length > 1)
    r.push(c.ids)
  return r
}, [])

console.log(prettify(group(data)))      // OP data
console.log(prettify(group(testData)))  // Test data

La raison de cette version est due au testData fourni par @Mark qui a le 2ème élément ne correspondant pas au premier mais correspondant au 3ème qui correspond en fait au 1er ... donc ils devraient tous être des hits.

Pour y arriver une fois que nous avons trouvé une correspondance, nous recherchons des correspondances de cette même correspondance initiale et poussons dans le même groupe afin que nous puissions avoir la quantité maximale de données sur laquelle correspondre.

Le résultat est qu'une fois que nous obtenons le premier groupe avec le premier élément, nous trouvons et poussons également le 3e et à partir de là, il est beaucoup plus facile de faire correspondre le 2e. La logique est un peu plus complexe et j'imagine moins performante.

0
Akrion 21 nov. 2018 à 07:50

Toute réponse qui itère sur chacune des n entrées, puis sur une liste croissante de m groupes à comparer, aura les performances les plus défavorables de O(n*m) (trouvée lorsqu'il n'y a pas deux entrées qui correspondent à n'importe quel terme).

Toute réponse qui itère sur chaque entrée, puis sur les groupes, et utilise des tableaux pour tester les valeurs correspondantes parmi les q options devra en outre payer une pénalité de O(q) par correspondance. Dans le pire des cas, avec tous les e-mails identiques et tous les téléphones différents, cela signifie O(n*m).

Je crois que cette réponse est O(n), car en supposant que le nombre de champs avec lesquels correspondre est une constante (dans ce cas, 3: name, phone et email), toutes les opérations dans la boucle principale, qui est exécutée une fois par entrée, sont O(1).

Il y a une complication supplémentaire pour corriger le fait que, tard dans le processus, nous pouvons trouver un pont entre deux (voire 3) groupes, car les entrées peuvent correspondre sur différents champs avec des entrées de différents groupes. Cela peut se produire plusieurs fois. Pour éviter d'avoir à reconstruire des groupes pendant la boucle principale, nous laissons la fusion à la toute fin, où nous construisons d'abord une carte de ce que le groupe finit par où, puis déplaçons finalement tous les ID d'entrée vers leur groupe final. Tout cela peut être fait dans O(m), avec m le nombre de groupes; avec un O(n) supplémentaire lors de la copie effective des ID d'entrée dans les groupes fusionnés: dans l'ensemble, nous sommes toujours sur le territoire O(n).

La dernière ligne crée des tableaux d'ID à partir des groupes fusionnés et filtre ceux qui ne contiennent pas plus d'un élément.

const data = [
    {id:1,name:'John',phone:'11111111',email:'aaaa@test.com'},
    {id:2,name:'Marc',phone:'99999999',email:'bbbb@test.com'},
    {id:3,name:'Ron',phone:'99999999',email:'aaaa@test.com'},
    {id:4,name:'Andrew',phone:'55555555',email:'dddd@test.com'},
    {id:5,name:'Wim',phone:'99999999',email:'gggg@test.com'},
    {id:6,name:'Marc',phone:'33333333',email:'cccc@test.com'},
    {id:7,name:'Dan',phone:'44444444',email:'cccc@test.com'}
];

const groups = function(inputs) {

    let valuesToGroups = new Map(
        ['name', 'phone', 'email'].map(key => [key, new Map()]));
    let groups = new Map();
    let pendingMerges = [];
    for (const entry of inputs) {
        let group = undefined;
        let found = [];
        for (const [key, valueMap] of valuesToGroups) {
            // look up value in values-index for current key
            group = valueMap.get(entry[key]);
            if (group !== undefined) {
                found.push(group);
                // not breaking allows groups to be merged
            }
        }
        if (found.length === 0) {
            // not found: create new group
            group = groups.size;
            groups.set(group, [entry.id]);
        } else {
            // found: add entry to chosen group
            group = found[0];
            groups.get(group).push(entry.id);
            if (found.length > 1) {
                pendingMerges.push(found);
            }
        }
        // add entry's values to index, pointing to group
        for (const [key, valueMap] of valuesToGroups) {
            valueMap.set(entry[key], group); 
        }        
    }
    // do pending merges; initially, all groups are stand-alone
    let merges = new Map(Array.from(groups.keys()).map(k => [k, k]));
    for (const merge of pendingMerges) {
        // contents will go to the lowest-numbered group
        const sorted = merge.map(groupId => merges.get(groupId)).sort();
        sorted.forEach(groupId => merges.set(groupId, sorted[0]));
    }
    const cleanGroups = new Map();
    groups.forEach((value, key) => { 
        const k = merges.get(key); 
        if ( ! cleanGroups.has(k)) {
            cleanGroups.set(k, []);
        }
        value.forEach(id => cleanGroups.get(k).push(id))
    })
    // return only non-empty groups
    return [... cleanGroups].filter(g => g[1].length>1).map(g => [... g[1]]);
}(data);

console.log(""+JSON.stringify(groups))
// output is [[1,2,3,5,6,7]]
2
tucuxi 21 nov. 2018 à 11:25