Fusionner des listes qui partagent des éléments communs
Mon entrée est une liste de listes. Certains d'entre eux partagent des éléments communs, par exemple.
L = [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
J'ai besoin de fusionner toutes les listes, qui partagent un élément commun, et répétez cette procédure tant qu'il n'y a plus de listes avec le même élément. J'ai pensé à utiliser les opérations booléennes et une boucle while, mais ne pouvait pas arriver à une bonne solution.
Le résultat final devrait être:
L = [['a','b','c','d','e','f','g','o','p'],['k']]
- Qu'entendez-vous par fusion? L'Union? Pouvez-vous montrer le résultat que vous attendez pour votre exemple de données?
- Dans votre exemple, voulez-vous arrêter lorsque vous rencontrez
[k]
? Ou allez-vous par le biais de toutes vos listes? - ce sujet de la liste
[[a, b, c], [b, d, e], [d, f, g]]
. Devraient tous être fusionnées en bas à une liste? le premier et le dernier listes n'ont pas un élément en commun. - De toute façon, la complexité sera, au mieux, expotential (probablement le pire). Comment au sujet de l'utilisation de sets au lieu de faire au moins la vérification d'éléments communs rapide?
- Vous passez par l'ensemble de la liste une fois, de rejoindre toutes les listes qui ont un élément commun (si bool(ensemble(A) & set(B)) == True). Après que vous vérifiez de nouveau et de nouveau aussi longtemps que vous ne pouvez pas rejoindre le reste de la liste. Si il y a une liste à n éléments communs à d'autres listes, nous la garder comme elle est.
InformationsquelleAutor Wistful Jesus | 2011-01-30
Vous devez vous connecter pour publier un commentaire.
Vous pouvez voir votre liste comme une notation pour un Graphe, c'est à dire
['a','b','c']
est un graphe avec 3 nœuds reliés les uns aux autres. Le problème que vous essayez de résoudre est de trouver les composantes connexes de ce graphe.Vous pouvez utiliser NetworkX pour ce, qui a l'avantage qu'il est à peu près garanti pour être correct:
Pour résoudre ce de manière efficace vous-même, vous devez convertir la liste en quelque chose de graphique-ish de toute façon, de sorte que vous pourriez aussi bien utiliser networkX depuis le début.
to_edges
fonction pourrait être remplacé parizip(part[:-1], part[1:])
.Algorithme:
De sorte que vous pouvez utiliser à la place de la liste. Le programme suivant devrait le faire.
first, *rest = l
construire est Python 3, de la permutation avecfirst, rest = l[0], l[1:]
semble fonctionner sur python 2.7Je suis tombé sur la même question d'essayer de fusionner les listes avec des valeurs communes. Cet exemple est peut-être ce que vous cherchez.
Il ne passe en boucle sur les listes une fois et les mises à jour de jeu de résultats comme il va.
#
Je pense que cela peut être résolu par la modélisation du problème sous forme de graphique. Chaque sous-liste est un nœud et les actions d'un bord à un autre nœud si les deux sous-listes ont certains éléments en commun. Ainsi, une fusion de sous-liste est fondamentalement un composant connecté dans le graphique. La fusion de tous les d'eux est tout simplement une question de trouver tous les composants connectés et de les répertorier.
Cela peut être fait par un simple traversal sur le graphique. Les deux BFS et DFS peut être utilisé, mais je suis en utilisant DFS ici, car il est un peu plus courte pour moi.
L = [['a','b','c','d','e','f','g','o','p'],['k']]
mais dans 3.5.3 ce code imprime[['a', 'c', 'b', 'p']]
. Je suis peut-être raté quelque chose? Mon post ci-dessus exécute des tests au hasard avec des entrées différentes, de sorte que vous pouvez vérifier que trop...Comme Jochen Ritzel souligné vous êtes à la recherche de composantes connexes dans un graphe. Voici comment vous pourriez la mettre en œuvre sans l'aide d'un graphique de la bibliothèque:
J'avais besoin pour effectuer le regroupement technique décrite par les OP des millions de fois, mais les grandes listes, et donc voulu déterminer laquelle des méthodes proposées ci-dessus est à la fois plus précis et le plus performant.
J'ai couru 10 essais pour la saisie des listes de taille moyenne à partir de 2^1 à 2^10 pour chaque méthode ci-dessus, en utilisant la même liste d'entrée pour chaque méthode, et de mesurer la moyenne d'exécution pour chaque algorithme proposé ci-dessus, en millisecondes. Voici les résultats:
Ces résultats m'a aidé à voir que des méthodes qui ont constamment un retour des résultats corrects, @de jochen est le plus rapide. Parmi ces méthodes qui ne sont pas systématiquement renvoyer des résultats corrects, mak est une solution souvent ne comprennent pas tous les éléments de saisie (c'est à dire la liste des membres de la liste sont manquants), et les solutions de braaksma, cmangla, et l'astérisque ne sont pas garantis pour être au maximum de fusionnés.
Il est intéressant de noter que les deux plus rapide, correcte, les algorithmes de les deux montant de upvotes à ce jour, dans correctement l'ordre de classement.
Voici le code utilisé pour exécuter les tests:
Et pour le traçage:
Ma tentative. A fonctionnel pour elle.
J'ai trouvé itertools une option rapide pour la fusion des listes et il a résolu ce problème pour moi:
Pour les grands ensembles de tri LL par la fréquence de la plupart des éléments communs au moins peut accélérer un peu les choses
C'est assez rapide solution sans dépendances. Il fonctionne comme suit:
Attribuer un numéro de référence unique à chacun de vos subsiste (dans ce cas, le premier indice de la sous-liste)
Créer un dictionnaire des éléments de référence pour chaque sous-liste, et pour chaque élément de chaque sous-liste.
Répéter la procédure suivante jusqu'à ce qu'il ne cause pas de changements:
3a. Aller à travers chaque élément de chaque sous-liste. Si l'élément actuel numéro de référence est différent du numéro de référence de ses sous-liste, l'élément doit faire partie de deux listes. Fusionner les deux listes (suppression de l'actuelle sous-liste de référence) et de définir le numéro de référence de tous les articles dans le courant de la sous-liste à être le numéro de référence de la nouvelle sous-liste.
Lorsque cette procédure entraîne pas de changements, c'est parce que tous les éléments font partie de exactement une liste. Car travailler ensemble est une diminution de la taille à chaque itération, l'algorithme se termine nécessairement.
Voici une série de tests pour ce code:
Noter que la valeur de retour est une liste de jeux.
Sans savoir très bien ce que vous voulez, j'ai décidé de deviner juste vous dire: je veux trouver chaque élément, juste une fois.
De sortie ressemble à ceci:
.__class__ == list
l'air si incroyablement mauvais. À tout le moins,isinstance(sub, list)
. Si seulement comme une question de principe. (Aussi, vous pourriez/devriez utiliser un jeu au lieu d'un dict avec de fausses valeurs.)C'est peut-être plus simple, plus rapide de l'algorithme et semble bien fonctionner -
Je manque un non quirurgic version. Je l'ai posté sur 2018 (7 ans plus tard)
Un facile et understable approche:
1) faire le produit cartésien ( cross join ) la fusion de deux si les éléments en commun
2) supprimer dup
Vous pouvez utiliser networkx bibliothèque, car c'est un la théorie des graphes et les composants connectés problème:
De sortie: