Valeurs communes de tuple dans une liste

Version imprimable

12/04/2019, 15h18
marsouin_89

Valeurs communes de tuple dans une liste

Bonjour à tous,

Autodidacte, je ne suis pas un grand spécialiste de Python, d'où ma venue vers vous.

J'ai des tuples qui sont dans une liste et j'aimerais avoir une liste des tuples qui ont une valeur commune.

Exemple sachant que la valeur commune n'est pas forcément à la même position dans le tuple :

Code:

values = [(A, B), (C, D), (D, E), (F, G), (E, F), (L, M), (O, P), (N, O), (M, N), (R, S)]

J'aimerais donc obtenir :

Code:

result = [(A, B), (C, D, E, F, G), (L, M, N, O, P), (R, S)]

À priori, lambda pourrait être la solution mais je n'arrive pas à mettre en oeuvre cette procédure.

Quelqu'un pourrait il m'orienter, cela fait 3 jours que je cherche partout sur le Net, mais j'avoue que je sèche.

Merci beaucoup
12/04/2019, 15h43
wiztricks

Salut,

Il faut déjà décrire un algorithme/méthode qui permette de vérifier la propriété le tuple X et le tuple Y ont une valeur commune. Ce qui peut se traduire par une fonction qui vérifie "bourrin" si un des éléments de X est dans Y ou l'utilisation d'ensembles (les set de Python).

Puis vous essayez de voir comment passez de (C, D), (D, E), (F, G), (E, F) à (C, D, E, F, G) "à la main"... Et une fois que vous aurez joué avec quelques exemples, vous pourrez envisager de coder quelque chose (et le montrer).

- W
12/04/2019, 15h51
marsouin_89

Bonjour wiztricks,

Merci pour la rapidité de réponse.

Oui, en effet, j'avais imaginé la solution de la sorte et c'est bien là qu'est mon problème.
Comment mouliner tout cela ?

Merci

Bonjour,

Sans que la solution soit très élégante, en voici une:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
values = [('A', 'B'), ('C', 'D'), ('D', 'E'), ('F', 'G'), ('E', 'F'), ('L', 'M'), ('O', 'P'), ('N', 'O'), ('M', 'N'), ('R', 'S')]
print(values)
 
while True:
    modif = False
    for i in range(0, len(values)):
        fin = values[i][-1] # derniere valeur de l'élément i 
        for j in range(0, len(values)):
            if i==j:
                continue # valeur de j suivante
            deb = values[j][0] # première valeur de l'élément j
            if deb==fin:
                values[i] += values[j][1:] # on concatène les 2 sous-listes
                values.pop(j) # on retire la 2ème sous-liste
                modif = True # on indique qu'on a fait une modif
                break # on quitte la boucle j
        if modif:
            # la liste a été modifiée dans la boucle j
            break # : on quitte la boucle i
    if not modif:
        # aucune modif dans la double boucle i et j: on a fini
        break
 
    # affichage de mise au point
    print(values)
 
# résultat final
print(values)

Ce qui affiche:

Code:

1
2
3
4
5
6
7
8
[('A', 'B'), ('C', 'D'), ('D', 'E'), ('F', 'G'), ('E', 'F'), ('L', 'M'), ('O', 'P'), ('N', 'O'), ('M', 'N'), ('R', 'S')]
[('A', 'B'), ('C', 'D', 'E'), ('F', 'G'), ('E', 'F'), ('L', 'M'), ('O', 'P'), ('N', 'O'), ('M', 'N'), ('R', 'S')]
[('A', 'B'), ('C', 'D', 'E', 'F'), ('F', 'G'), ('L', 'M'), ('O', 'P'), ('N', 'O'), ('M', 'N'), ('R', 'S')]
[('A', 'B'), ('C', 'D', 'E', 'F', 'G'), ('L', 'M'), ('O', 'P'), ('N', 'O'), ('M', 'N'), ('R', 'S')]
[('A', 'B'), ('C', 'D', 'E', 'F', 'G'), ('L', 'M', 'N'), ('O', 'P'), ('N', 'O'), ('R', 'S')]
[('A', 'B'), ('C', 'D', 'E', 'F', 'G'), ('L', 'M', 'N', 'O'), ('O', 'P'), ('R', 'S')]
[('A', 'B'), ('C', 'D', 'E', 'F', 'G'), ('L', 'M', 'N', 'O', 'P'), ('R', 'S')]
[('A', 'B'), ('C', 'D', 'E', 'F', 'G'), ('L', 'M', 'N', 'O', 'P'), ('R', 'S')]

Le principe est basique: on fait autant de boucle i et j jusqu'à ce qu'il n'y ait plus aucune correspondance (donc modification) trouvée.

[edit]: j'ai fait ça en Python 3 => peut-être faut-il faire quelques modifs? (range => xrange?)

Salut.

Et l'idée de wiztricks d'utiliser les sets pourrait être par ex.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
set_values = tuple(set(n) for n in sorted(values))
temp_values = []
 
for s in set_values:
    for n in temp_values:
        if n & s:
            n |= s
            break
    else:
        temp_values.append(s)
 
new_values = [tuple(sorted(n)) for n in temp_values]
print(new_values)

12/04/2019, 23h55
marsouin_89

Bonsoir tyrtamos,

Impressionnant de faire des analyses pareils.
En tout cas, un grand merci pour ce code.

En première approche, cela devrait répondre à mon besoin.
Cela dit, je dois faire encore quelques tests.
Dans mon code, les tuples sont en réalités des objets géographiques qui contiennent des coordonnées.
Je dois alors adapter le code pour avoir le premier et dernier objet point de mon entité géographique et cela devrait fonctionner.
A priori, sur mes premiers tests, j'aurais juste un souci avec la fonction pop.
Je suis en python 2.6 et je vais faire quelques adaptations.

Je laisse le fil ouvert pour le moment le temps de finir mes tests.

Bistouille, je viens juste de voir ton fil. Je le testerais également et je vous tiens tous au courant.

Encore merci et bonne soirée.

Salut,
Citation:
Envoyé par bistouille
Et l'idée de wiztricks d'utiliser les sets pourrait être par ex.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 set_values = tuple(set(n) for n in sorted(values)) temp_values = [] for s in set_values: for n in temp_values: if n & s: n |= s break else: temp_values.append(s) new_values = [tuple(sorted(n)) for n in temp_values] print(new_values)
Très joli ... mais si c'est le sort qui est la clef, l'histoire pourrait être autre.

La logique est de prendre chacun des éléments de set_values et tester s'ils ont une intersection avec un des éléments de temp_values.
Si c'est le cas, on fait l'union, sinon on l'ajoute à temp_values, et on réitère.

Mais en fait, comme c'est ordonné, il suffit de tester l'intersection avec le dernier élément. Ce qui évite de boucler deux fois:
Code:

1 2 3 4 5 6 7 8 c = set_values[0] for n in set_values[1:]: if c & n: c |= n else: temp_values.append(c) c = n temp_values.append(c)
Et du coup, on réduit la complexité de O(n²) (dans les mauvais cas) à O(n). Ce qui est toujours çà de pris (même si le code est moins joli).

- W

13/04/2019, 14h44
bistouille

En effet, c'est un peu plus optimisé (25% de gain), merci de la réflexion apportée à ce bout de code.

Bonsoir à tous,

J'ai enfin réussi à mettre en oeuvre le code de tyrtamos en l'adaptant à mes contraintes particulières.
En fait, ce code est utilisé avec le logiciel de cartographie ArcGIS.
L'idée est de pouvoir fusionner des objets géométriques linéaires.
Dans l'idée, chaque tuple était sensé représenté les coordonnées du premier et dernier point de chaque linéaire sachant que chaque linéaire peut avoir plusieurs points de construction.
Je souhaitais donc pouvoir fusionner en un seul élément tous les linéaires qui se connectent entre eux et qui ont le même nom.
Du coup, avec ce code, je peux avoir un ou plusieurs linéaires comme résultat.
J'ai donc intégrer dans le code de tyrtamos des fonctions spécifiques à mon logiciels (touches et union).
Ces fonctions sont l'équivalent de set que m'avait conseillé wiztricks si j'ai bien compris les fonctions set.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 def dissolvePolylines(polylines): while True: modif = False # Parcours chaque polyligne for i in range(0, len(polylines)): fin = polylines[i] # Géométrie de l'élément i # Parcours chaque polyligne pour les comparer avec la 1° boucle for j in range(0, len(polylines)): # Si l'index des 2 boucles est le même if i == j: continue # Valeur de j suivante deb = polylines[j] # Géométrie de l'élément j # Si les géométries se touches if deb.touches(fin): # On fusionne les 2 géométries polylines[i] = fin.union(deb) # Supprime la géométrie de l'élément j del polylines[j] modif = True # On indique qu'on a fait une modif break # On quitte la boucle j if modif: # La liste a été modifiée dans la boucle j break # : On quitte la boucle i if not modif: # Aucune modif dans la double boucle i et j: on a fini break # Retour de résultat return polylines
Merci à vous tous pour vos conseils. Cela faisait 4 jours que je galérais sur une solution.