Récupérer des inclusions en python

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 :roll:

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 :

Citation:

---

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 (:mouarf:) ou encore Loïc dans Toto.
Je voudrai par exemple écrire dans un fichier de sortie :

Citation:

---

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

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:

---

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

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:

---

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 !

Bonjour,

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

Voilà une solution possible:

Code:

---

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']]

---

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

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 :aie:
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:

---

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

---

et j'aimerai obtenir cela:

Code:

---

[1,4],[5,12]

---

Merci à vous

Bonjour,

J'ai adapté aux nouvelles données:

Code:

---

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

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

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

Bonjour,

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

Code:

---

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]]

---

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 :aie:

Voici ma liste de départ:

Code:

---

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

---

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

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.

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

Aaaaah, ça commence à s'éclaircir!

Nouveau code:

Code:

---

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!

Un grand merci Tyrtamos je vais travailler tout ça :ccool:

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:

---

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:

---

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:

---

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

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 :ccool: