Discussion :

[marsouin_89]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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

[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

[tyrtamos]

Bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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?)

[bistouille]

Salut.

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

[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.

[wiztricks]

Salut,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[bistouille]

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

[marsouin_89]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.