Je m'adresse à vous car je suis confronté à un type de problème que je n'ai jamais rencontré. En deux mots, je dois reconstituer des "chaînes" à partie de "maillons éparpillés".
Je suis capable de mettre au point une procédure "triviale" qui fonctionne. Cela dit, cette procédure n'est pas utilisable avec un très grand nombre de maillons... La durée de l'opération serait beaucoup trop importante.
Je suppose qu'il existe des algorithmes pour résoudre ce problème. Il me semble que ce genre d'opération est effectuée en génie génétique, pour reconstituer des séquences de gènes. J'ai effectué des recherches dans cette direction, mais sans succès.
Donc, si quelqu'un peut me donner une piste, je suis preneur!
J'ai essayé de formaliser le problème de façon précise :
Une liste chaînée simple est constituée de maillons :
Les maillons [x1,y1] et [x2,y2] sont liés si la relation suivante est vérifiée : y1=x2.
Description du problème :
Soit "E" un ensemble de N maillons.
Dans l'ensemble "E", les maillons sont répartis de manière arbitraire. Autrement dit, les maillons sont "mélangés".
Par exemple :
E = ([E,F], [A,B], [C,D], [B,C], [D,E]).
Les maillons présents dans l'ensemble "E" forment plusieurs chaînes distinctes.
Par exemple :
E = ([E,F], [A,B], [C,D], [B,C], [D,E], [Y,Z], [X,Y]).
"E" présente deux chaînes :
[A,B] => [B,C] => [C,D] => [D,E] => [E,F]
[X,Y] => [Y,Z]
Question : Comment regrouper les maillons de l'ensemble "E" en chaînes?
Par exemple :
Le traitement de l'ensemble E = ([E,F], [A,B], [C,D], [B,C], [D,E], [Y,Z], [X,Y]) produit deux groupes :
Le groupe ([A,B], [B,C], [C,D], [D,E], [E,F])
Et le groupe ([X,Y], [Y,Z]).
Contrainte :
Le nombre de maillons est grand (entre 500000 et 6000000).
En majorité, les chaînes présentent des petites tailles (5 maillons). Mais il y en a de très grandes (ex: 600 maillons).
