filtrer les ensembles disjoints ?

Dans fr.comp.lang.python, Joh écrivit:

bonjour,

je me retrouve face au probleme suivant, je souhaiterai filtrer un
ensemble d'ensembles en ne conservant que ceux qui sont totalement
disjoints :

par exemple pour [(0, 15) (6, 12), (6, 21), (18, 21)] ne conserver que
[(6, 12), (18, 21)]

(concretement il s'agit d'etendue (0 à 15) , (6 à 12) , etc.

je ne sais pas par quel bout commencer peut etre y a t il quelque
chose a faire avec des ensembles avec intersections ? quelqu'un aurait
il une piste ?

Et s'il y avait plusieurs réponses possibles ?
[(0, 13), (5, 17), (15, 36), (19, 42)]
=> [[(0, 13), (15, 36)], [(5, 17), (19, 42)]]
Je pense que sans contraintes ce problème est NP-complet.

Quel est l'énnoncé du TP ?
--
Encolpe DEGOUTE
http://colpi.info
Logiciels libres, hockey sur glace et autres activités cérébrales

on peut tirer parti du module sets, qui arrive en implémentation C dans
python 2.4 :

#!/usr/bin/env python

import sets

data = [ sets.Set(s) for s in [ (0, 15), (6, 12), (6, 21), (18, 21) ] ]

result = sets.Set()

blackset = sets.Set()

for set in data:
global_intersect = sets.Set()
for s in data:
if not (s in blackset or (set == s)):
inter = set & s
if inter:
global_intersect.add(s)
blackset |= inter
if global_intersect:
print set, " has intersection with ", global_intersect
else:
result.add(set)

print result


Joh wrote:

bonjour,

je me retrouve face au probleme suivant, je souhaiterai filtrer un
ensemble d'ensembles en ne conservant que ceux qui sont totalement
disjoints :

par exemple pour [(0, 15) (6, 12), (6, 21), (18, 21)] ne conserver que
[(6, 12), (18, 21)]

(concretement il s'agit d'etendue (0 à 15) , (6 à 12) , etc.

je ne sais pas par quel bout commencer peut etre y a t il quelque
chose a faire avec des ensembles avec intersections ? quelqu'un aurait
il une piste ?

merci a vous.

raah ça m'apprendra à poster au réveil ;o) ! le placement du test de
blackset n'était pas très judicieux ! voici mieux :

#!/usr/bin/env python

import sets

data = sets.Set([ sets.Set(s) for s in [ (0, 15), (6, 12), (6, 21), (18,
21) ] ])

result = sets.Set()

blackset = sets.Set()

for set in data:
if not set in blackset:
global_intersect = sets.Set()
for s in data - blackset:
inter = set != s and set & s or None
if inter:
global_intersect.add(s)
blackset |= inter
if not global_intersect:
result.add(set)

print result


---
toujours attendre le troisième café avant de coder :o)