Fusion de tableaux avec un élément commun

Question

Je souhaite fusionner des tableaux avec un élément commun. Je liste des tableaux comme ceci:

List<int[]> arrList = new List<int[]> 
{ 
    new int[] { 1, 2 }, 
    new int[] { 3, 4, 5 }, 
    new int[] { 2, 7 }, 
    new int[] { 8, 9 }, 
    new int[] { 10, 11, 12 }, 
    new int[] { 3, 9, 13 } 
}; 

et je voudrais fusionner ces tableaux comme celui-ci:

List<int[]> arrList2 = new List<int[]> 
{ 
    new int[] { 1, 2, 7 }, 
    new int[] { 10, 11, 12 }, 
    new int[] { 3, 4, 5, 8, 9, 13 } //order of elements doesn't matter 
}; 

Comment faire?

Answer 1

Laissez chaque nombre être un sommet dans le graphe étiqueté. Pour chaque tableau, connectez les sommets pointés par les nombres dans le tableau donné. Par exemple. tableau donné (1, 5, 3) crée deux arêtes (1, 5) et (5, 3). Ensuite, trouvez tous les composants connectés dans le graphique (voir: http://en.wikipedia.org/wiki/Connected_component_(graph_theory))

Answer 2

Utilisez Disjoint-Set Forest data structure. La structure de données prend en charge trois opérations:

• MakeSet(item) - crée un nouveau jeu avec un seul élément
• Find(item) - Étant donné un élément, regardez un ensemble.
• Union(item1, item2) - Étant donné deux éléments, connecte ensemble les ensembles auxquels ils appartiennent.

Vous pouvez parcourir chaque tableau et appeler le Union sur son premier élément et chaque élément que vous trouvez après lui. Une fois que vous avez terminé avec tous les tableaux dans la liste, vous serez en mesure de récupérer les ensembles individuels en passant à travers tous les numéros à nouveau, et en appelant Find(item) sur eux. Numéros les Find sur lequel produire le même ensemble devrait être mis dans le même tableau.

Cette approche finit la fusion en O(α(n)) amorti (α se développe très lentement, donc pour toutes les applications pratiques, il peut être considéré comme une petite constante).

Answer 3

Je suis assez sûr ce n'est pas la meilleure solution et la plus rapide, mais fonctionne.

static List<List<int>> Merge(List<List<int>> source) 
{ 
    var merged = 0; 
    do 
    { 
     merged = 0; 
     var results = new List<List<int>>(); 
     foreach (var l in source) 
     { 
      var i = results.FirstOrDefault(x => x.Intersect(l).Any()); 
      if (i != null) 
      { 
       i.AddRange(l); 
       merged++; 
      } 
      else 
      { 
       results.Add(l.ToList()); 
      } 
     } 

     source = results.Select(x => x.Distinct().ToList()).ToList(); 
    } 
    while (merged > 0); 

    return source; 
} 

Je l'ai utilisé List<List<int>> au lieu de List<int[]> pour obtenir la méthode AddRange disponible.

Utilisation:

var results = Merge(arrList.Select(x => x.ToList()).ToList()); 

// to get List<int[]> instead of List<List<int>> 
var array = results.Select(x => x.ToArray()).ToList();