Comment fusionner des listes avec des éléments qui se chevauchent à l'aide de la théorie des graphes ?

Fusionner des listes avec des éléments partagés : une approche théorique des graphes

Étant donné une collection de listes, dont certaines contiennent des éléments qui se chevauchent, l'objectif consiste à les consolider dans un ensemble de listes comprenant l'ensemble complet des éléments uniques des listes d'origine. Par exemple, considérons la liste de listes d'entrée suivante :

L = [['a', 'b', 'c'], ['b', 'd', 'e'], ['k'], ['o', 'p'], ['e', 'f'], ['p', 'a'], ['d', 'g']]

La tâche consiste à fusionner les listes qui partagent des éléments communs jusqu'à ce qu'aucune liste ne puisse plus être combinée. Le résultat souhaité serait :

L = [['a', 'b', 'c', 'd', 'e', 'f', 'g', 'o', 'p'], ['k']]

Bien que des opérations booléennes et des boucles while puissent être utilisées, une approche plus efficace peut être trouvée en visualisant les listes sous forme de graphique. Dans une représentation graphique, chaque liste correspond à un ensemble de nœuds reliés par des arêtes. Par conséquent, le problème se traduit par la recherche des composants connectés dans ce graphique.

Une solution consiste à utiliser NetworkX, une bibliothèque robuste pour l'analyse de graphiques, comme démontré ci-dessous :

<code class="python">import networkx 
from networkx.algorithms.components.connected import connected_components

def to_graph(l):
    G = networkx.Graph()
    for part in l:
        # each sublist is a bunch of nodes
        G.add_nodes_from(part)
        # it also imlies a number of edges:
        G.add_edges_from(to_edges(part))
    return G

def to_edges(l):
    """ 
        treat `l` as a Graph and returns it's edges 
        to_edges(['a','b','c','d']) -> [(a,b), (b,c),(c,d)]
    """
    it = iter(l)
    last = next(it)

    for current in it:
        yield last, current
        last = current    

G = to_graph(l)
print(connected_components(G))
# prints [['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p'], ['k']]</code>

En tirant parti de la puissance de la théorie des graphes, NetworkX gère efficacement la tâche, garantissant l'exactitude et l'efficacité.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!