Récupérer des inclusions en python

**michel42** · 11/03/2012, 12h19

Bonjour à tous,

je suis nouveau dans le monde de Python et je commence mes premiers scripts. Il s'avère que je suis bloqué sur une problématique assez simple, je pense qu'une notion a dû m'échapper

Je travail sur un fichier texte qui contient 3 colonnes, la première contient une position de début, la seconde une position de fin, et enfin la troisième un identifiant, du genre :

12___15____Laurent
14___15___Michel
25___32___Toto
27___31___Loïc

(mon fichier ne contient pas d'underscore c'était juste pour séparer les données)

J'essaie de regrouper ensemble tous les IDs qui sont inclus les uns dans les autres, par exemple Michel dans Laurent (

) ou encore Loïc dans Toto.
Je voudrai par exemple écrire dans un fichier de sortie :

12___15____Laurent, Michel
25___32___Toto, Loïc

Niveau algo ça va, je regarde une colonne (par exemple la première, et si je trouve une position de début supérieure ou égale à cette position ET une position de fin inférieure ou égale, alors je suis bien dans le cas d'une inclusion.

Ce que je n'arrive pas à faire c'est comparer entre eux les éléments d'une même liste, voila ce que j'ai fais: j'ai lu mon fichier et j'ai mis dans 3 listes différentes mes 3 colonnes.

J'arrive à parcourir ma liste contenant mes positions de début mais je n'arrive pas à comparer les élements entre eux (sont'ils égaux etc...).

Peut être auriez vous une idée quant à la marche à suivre.

Cordialement,

Michel

**VinsS** · 11/03/2012, 12h51

Salut,

En fait tes valeurs sont des ranges, si je comprends bien.

Si tu en fais des set(), tu peux les comparer directement entre eux

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
 
>>> a = set(range(10, 16))
>>> b = set(range(12, 15))
>>> c = set(range(11, 20))
>>> a > b
True
>>> a > c
False
>>> b > a
False
>>> b > c
False
>>> b <= a
True
>>> b <= c
True

Voir les opérations de comparaison ici:
http://docs.python.org/library/stdty...et#comparisons

**michel42** · 11/03/2012, 13h00

Bonjour,

merci pour votre aide je vais étudier cette solution !

J'ai regardé le lien, je connais ces opérateurs, mais il m'est impossible de faire quelque chose comme ça :

Code :

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

1
2
3
for i in debut:
      if i == i :
             ...

Je ne peux pas comparer directement les élements d'une même liste entre eux, enfin je ne crois pas. Je vais étudier la fonction set merci à vous !

**tyrtamos** · 11/03/2012, 14h43

Bonjour,

Ça ressemble à un tableau de présence: qui était dans cette salle en même temps que... ?

Voilà une solution possible:

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
L = [[12, 15, "Laurent"],
     [14, 15, "Michel"],
     [25, 32, "Toto"],
     [27, 31, "Loïc"]]
 
inclusions = []
for i, liste in enumerate(L):
    deb, fin, nom = liste
    for j, liste2 in enumerate(L):
        if j!=i:
            deb2, fin2, nom2 = liste2
            if deb2>=deb and fin2<=fin:
                inclusions.append([deb, fin, nom, nom2])
print inclusions
[[12, 15, 'Laurent', 'Michel'], [25, 32, 'Toto', u'Loïc']]

**michel42** · 11/03/2012, 15h08

Merci beaucoup pour votre solution c'est tout à fait ce que je cherchais

**michel42** · 19/03/2012, 16h08

Bonjour,

pardonnez ma réponse tardive mais j'aurai voulu savoir si vous pouviez me détailler un peu votre code. Je pensais avoir compris la mécanique mais lorsque j'ai voulu le réutiliser dans un cas différent je n'arrivais pas à obtenir de résultats

J'ai les mêmes fichiers d'entrées sauf que je n'ai pu de noms, juste les intervalles, j'ai donc enlevé les variables relatives aux noms dans le code, mais la liste que j'ai en retour est composée de tous les intervales de base en plusieurs exemplaires.

Pour rappel je dispose de ça:

Code :

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

[1,3],[2,4],[5,8],[5,12]...

et j'aimerai obtenir cela:

Code :

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

[1,4],[5,12]

Merci à vous

**tyrtamos** · 19/03/2012, 21h40

Bonjour,

J'ai adapté aux nouvelles données:

Code :

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

1
2
3
4
5
6
7
8
9
L = [[1,3],[2,4],[5,8],[5,12]] 
inclusions = []
for i, (deb, fin) in enumerate(L):
    for j, (deb2, fin2) in enumerate(L):
        if j!=i:
            if deb2>=deb and fin2<=fin:
                inclusions.append([deb, fin])
print inclusions
[[5, 12]]

Donc, je trouve [5, 12] (à cause de [5, 8]), mais pas [1, 4]. Auriez-vous changé les règles?
???

**michel42** · 19/03/2012, 23h12

Veuillez m'excuser mon explication n'était pas claire

En réalité je souhaiterai trouver tous les intervalles non chevauchant,

[5,8],[5,12] donne donc bien [5,12] mais [1,3],[2,4] donne également [1,4].

J'ai fais des recherches sur internet "python overlaping", j'ai trouvé beaucoup de questions mais très peu de réponses, même si le principe est simple, je reconnais que niveau code je sèche

**tyrtamos** · 20/03/2012, 06h23

Bonjour,

Effectivement, l'algorithme a changé (voir ligne 6 et 7). Voilà le nouveau code:

Code :

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

1
2
3
4
5
6
7
8
9
L = [[1,3],[2,4],[5,8],[5,12]] 
inclusions = []
for i, (deb, fin) in enumerate(L):
    for j, (deb2, fin2) in enumerate(L):
        if j!=i:
            if deb<=deb2<=fin and fin2>=fin:
                inclusions.append([deb, fin2])
print inclusions
[[1, 4], [5, 12]]

**michel42** · 20/03/2012, 10h02

Re bonjour,

en effet le résultat obtenu est le bon, pourtant lorsque je test le code sur mes données plus rien ne va, alors que je suis la même démarche

Voici ma liste de départ:

Code :

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

[[1428, 2111], [2332, 7328], [2332, 4496], [2332, 3480], [7098, 8040], [8045, 9060], [8617, 9946], [9151, 9946], [9937, 15715], [11300, 15715], [13520, 15715], [16041, 20969], [16041, 18964], [20942, 24767], [24761, 28024], [27850, 30494], [27850, 28865], [30143, 31822], [30489, 31822], [31433, 31822], [32157, 41577], [41614, 44514], [44375, 45594], [45802, 49218], [48132, 49218], [49564, 50734], [50690, 51963], [51961, 53144], [53150, 54672], [54812, 58837], [54812, 58127], [54812, 56504], [54812, 55750], [58684, 59762], [59732, 61839], [63625, 65263], [65258, 65795], [65789, 70988], [69977, 70988], [71035, 76362], [72205, 75105], [73847, 75115], [76123, 79464], [76430, 79464], [77480, 79464], [79248, 79464], [79769, 81235], [80899, 85537], [83338, 85537], [85543, 88313], [85543, 86583], [88251, 91398], [90776, 91398], [91483, 94366], [91483, 93947], [91483, 93085], [91483, 92367], [95042, 107984], [95210, 96687], [101586, 106712], [113869, 115895], [116600, 119318], [117693, 119318], [119385, 120926], [120614, 120926], [120927, 121512], [121953, 123979], [131136, 136262]]

Et celle retournée en sortie:

Code :

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

[[2332, 8040], [2332, 7328], [2332, 7328], [2332, 4496], [8045, 9946], [8617, 9946], [8617, 15715], [9151, 15715], [9937, 15715], [9937, 15715], [11300, 15715], [16041, 24767], [16041, 20969], [20942, 28024], [24761, 30494], [24761, 28865], [27850, 31822], [27850, 31822], [27850, 30494], [30143, 31822], [30143, 31822], [30489, 31822], [41614, 45594], [45802, 49218], [49564, 51963], [50690, 53144], [54812, 59762], [54812, 58837], [54812, 58837], [54812, 58127], [54812, 58837], [54812, 58127], [54812, 56504], [58684, 61839], [63625, 65795], [65258, 70988], [65789, 70988], [71035, 79464], [72205, 75115], [76123, 79464], [76123, 79464], [76123, 79464], [76430, 79464], [76430, 79464], [77480, 79464], [79769, 85537], [80899, 85537], [85543, 91398], [85543, 88313], [88251, 91398], [91483, 94366], [91483, 94366], [91483, 93947], [91483, 94366], [91483, 93947], [91483, 93085], [116600, 119318], [119385, 120926]]

Je précise que les données sont triées, ici l'intervalle [1428, 2111] à disparu, et j'obtiens [2332, 7328], [2332, 7328], [2332, 4496] au lieu de [2332,8040].

Voici un exemple fait manuellement, si je dispose de:
1428 2111
2332 7328
2332 4496
2332 3480
7098 8040
8045 9060

[1428,2111] est inclu nul part.
[2332,4496] et [2332,3480] sont inclus dans [2332,7328], de plus on peut concaténer [2332,7328] et [7098,8040] car 7098 < 7328, ce qui donnerait [2332,8040], soit en output:

[1428,2111],[2332,8040],[8045,9060].

**tyrtamos** · 20/03/2012, 10h39

Le problème, c'est que j'essaie de deviner ce que tu veux faire à partir des quelques exemples que tu donnes, et manifestement, je n'y arrive pas complètement.

Voilà le principe de mon code précédent:
1- chaque élément [di, fi] est comparé à tous les autres [dj, fj] avec i <> j.
2- si di<=dj<=fi et fj>fi alors, je garde [di, fj]

Si ça n'est pas exactement cela ou si tu as d'autres conditions: donnes tout sous cette forme! Et illustre par un petit exemple ou plusieurs.

**michel42** · 20/03/2012, 11h26

Re bonjour,

merci de l'attention que vous portez à mon problème, je vais essayer d'être le plus clair possible.

Considérons 2 intervalles [i,j] et [k,l]

si i<k et j<l alors je mets [i,j] de coté car il n'y a pas d'inlusions (par exemple [1428, 2111] et 2332 3480).

si i == k alors je garde l'intervalle possédant la fin la plus grande (par exemple [2332, 7328]
[2332, 4496] renverra -> [2332,7328].

De même si j==l je préseve l'intervalle avec le début le plus petit (éloigné) possible (par exemple [31041,32377] et [31988,32377] renverra -> [31041,32377].

si k<j l>j alors je concatènne en récupérant [i,l] (par exemple [32657,41948] et [41985,44885] renverra [32657,44885].

si k>i et l<j alors je supprime [k,l] puisqu'il est déjà contenu dans [i,j]

Et c'est ce dernier cas de figure qui est le plus fréquent, je pense qu'il y a une notion de récursivité la dessous, car à chaque nouvel intervalle crée par concaténation il peut y avoir une nouvelle concaténation etc... Pour résumé le seul moment où il n'y a pas de concaténation c'est quand j<k (mes données sont triées par ordre croissant donc si la fin de mon intervalle 1 est inférieur au début de mon interval 2 il ne peut pas y avoir inclusion.)

**tyrtamos** · 20/03/2012, 12h30

Aaaaah, ça commence à s'éclaircir!

Nouveau code:

Code :

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

1
2
3
4
5
6
7
8
9
10
inclusions = []
for i, (di, fi) in enumerate(L):
    for j, (dj, fj) in enumerate(L[i+1:]):
        if di==dj:
            inclusions.append([di, max(fi,fj)])
        elif fi==fj:
            inclusions.append([min(di,dj), fi])
        elif dj<fi and fj>fi:
            inclusions.append([di,fj])
print inclusions

Ça répond aux exemples, sauf pour le dernier: [41985,44885] qui ne satisfait pas la dernière condition: j'ai modifié en: [41900,44885], et dans ce cas, tout marche!

**michel42** · 20/03/2012, 16h22

Un grand merci Tyrtamos je vais travailler tout ça

**plxpy** · 21/03/2012, 07h39

Bonjour

je ne suis pas partisan d'un passage systématique par les classes mais, dans certains cas, elles permettent, aussi, de bien préparer les choses. L'algo peut se ramener à ça :

Code :

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

1
2
3
4
5
6
for i in range(len(L)-1,0,-1):
    for j in range(i-1,-1,-1):
        if not L[i].isdisjoint(L[j]):
            L[j] = L[j].union(L[i])
            del L[i]
            break

et en plus, ça marche avec une liste non triée d'intervalles.

Le script complet que j'ai particulièrement délayé et commenté :

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# -*- coding:utf-8 -*-
from pprint import pprint as pp
from random import randint
 
class Intervalle(object):
 
    def __init__(self,inf,sup,qui=list()):
        self.inf = inf
        self.sup = sup
        self.qui = qui
 
    def isdisjoint(self,other):
        # self et other sont-ils disjoints ?
        return self.sup < other.inf or other.sup < self.inf
 
    def union(self,other):
        # union de deux intevalles non disjoints
        assert not self.isdisjoint(other)
        return Intervalle(min(self.inf,other.inf),max(self.sup,other.sup),sorted(self.qui+other.qui))
 
    def __repr__(self):
        return "[%d;%d] (%s)" % (self.inf,self.sup,'' if not self.qui else ','.join(map(lambda q:"%02d"%q,self.qui)))
 
# ton exemple du post#10
L = [[1428, 2111], [2332, 7328], [2332, 4496], [2332, 3480], [7098, 8040], [8045, 9060], [8617, 9946], [9151, 9946], [9937, 15715], [11300, 15715], [13520, 15715], [16041, 20969], [16041, 18964], [20942, 24767], [24761, 28024], [27850, 30494], [27850, 28865], [30143, 31822], [30489, 31822], [31433, 31822], [32157, 41577], [41614, 44514], [44375, 45594], [45802, 49218], [48132, 49218], [49564, 50734], [50690, 51963], [51961, 53144], [53150, 54672], [54812, 58837], [54812, 58127], [54812, 56504], [54812, 55750], [58684, 59762], [59732, 61839], [63625, 65263], [65258, 65795], [65789, 70988], [69977, 70988], [71035, 76362], [72205, 75105], [73847, 75115], [76123, 79464], [76430, 79464], [77480, 79464], [79248, 79464], [79769, 81235], [80899, 85537], [83338, 85537], [85543, 88313], [85543, 86583], [88251, 91398], [90776, 91398], [91483, 94366], [91483, 93947], [91483, 93085], [91483, 92367], [95042, 107984], [95210, 96687], [101586, 106712], [113869, 115895], [116600, 119318], [117693, 119318], [119385, 120926], [120614, 120926], [120927, 121512], [121953, 123979], [131136, 136262]]
 
# j'en fais une liste d'objets "Intervalle"
L = [ Intervalle(i,s,[q]) for (q,(i,s)) in enumerate(L) ]
 
# liste désordonnée avec les indices entre 0 et len(L)-1
melange = list()
while len(melange) != len(L):
    candidat = randint(0,len(L)-1)
    if candidat not in melange:
        melange.append(candidat)
 
# L est maintenant dans le désordre
L = [ L[i] for i in melange ]
 
#============ début de l'algo proprement dit
 
# à reculons, de n-1 à 1 (pas 0)
for i in range(len(L)-1,0,-1):
 
    # à reculons, de i-1 à 0
    for j in range(i-1,-1,-1):
 
        # si les deux intervalles ne sont pas disjoints
        if not L[i].isdisjoint(L[j]):
 
            # j'en fais l'union (indice le + petit)
            L[j] = L[j].union(L[i])
 
            # je supprime l'élément de plus grand indice (i)
            # ca ne perturbe pas ma boucle for i
            del L[i]
 
            # j'arrete la recherche (boucle for j)
            break
 
#============ fin de l'algo proprement dit
 
 
# tri uniquement là pour l'affichage
L.sort(key=lambda e:e.inf)
 
pp(L)

L'affichage final :

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
[[1428;2111] (00),
 [2332;8040] (01,02,03,04),
 [8045;15715] (05,06,07,08,09,10),
 [16041;31822] (11,12,13,14,15,16,17,18,19),
 [32157;41577] (20),
 [41614;45594] (21,22),
 [45802;49218] (23,24),
 [49564;53144] (25,26,27),
 [53150;54672] (28),
 [54812;61839] (29,30,31,32,33,34),
 [63625;70988] (35,36,37,38),
 [71035;79464] (39,40,41,42,43,44,45),
 [79769;85537] (46,47,48),
 [85543;91398] (49,50,51,52),
 [91483;94366] (53,54,55,56),
 [95042;107984] (57,58,59),
 [113869;115895] (60),
 [116600;119318] (61,62),
 [119385;120926] (63,64),
 [120927;121512] (65),
 [121953;123979] (66),
 [131136;136262] (67)]

Dans la méthode "union" de la classe Intervalle, le "assert" est faux mais, testé sous idle, il était inopérant... C'est "assert not ..." qu'il faut mettre

**michel42** · 21/03/2012, 09h05

Impréssionnant, en effet plxpy c'est le résultat que j'attendais (après avoir fait le tri à la main), en mieux même car vous y avez ajouté le détail des concaténation subies. Je vais étudier votre code en détail, je m'aperçois que je ne maitrise pas encore assez bien le Python pour pouvoir produire ce genre de code. Problème résolu merci à vous

Récupérer des inclusions en python

Python

Discussions similaires

Partager

Partager