Bonjour,

Voici mon problème. J'ai des données de ce type :

  • un lien a deux éléments ordonnés ;
  • actuellement j'ai 35 éléments et 174 liens ;
  • un lien ne peut pas avoir deux éléments identiques ;
    Deux liens peuvent avoir des éléments identiques si ils sont ordonnés différemment :
    id : identifiant du lien
    fk_premier : 1er élément du lien
    fk_second : 2nd élément du lien
  • Une chaine est une suite de lien ;
  • Une chaine ne peut avoir qu'une seule fois un élément ;
  • Il ne faut pas qu'une chaine soit comprise dans une partie d'une autre chaine ;
  • Il faut trouver les chaines les plus longues possibles.


Exemple :

Lien1 (1er= élément 4, 2nd élément 8)
Lien2 (1er= élément 8, 2nd élément 2)
Lien3 (1er= élément 8, 2nd élément 5)
Lien4 (1er= élément 2, 2nd élément 4)
Lien5 (1er= élément 2, 2nd élément 6)

Toutes les chaines correctes:

lien1, lien2, lien5
lien1, lien3
lien2, lien4
lien4, lien1

Au niveau algo, j'ai du mal à trouver une solution correcte. J'arrive vite à des résultats énormes à stocker en mémoire : 250 000 chaînes possibles jusqu'à 6 liens, 850 000 chaînes possibles jusqu'à 7 liens, 2 770 000 chaînes possibles jusqu'à 8 liens.

Je ne sais pas si mes résultats sont cohérents au vu de mes données.

Mon algo :
  1. Récupère tous les liens ;
  2. pour chaque lien, création d'une chaine et recherche de la suite possible ;
  3. si 0 possibilité alors la chaine est finie. Si 1 une possibilité, alors on l'ajoute à la chaîne, si x possibilités alors on duplique la chaine x fois en y ajoutant la possibilité
  4. on boucle sur toutes les chaines en cours.


Mon algo est très long et très gourmand en mémoire. De plus il ne supprime pas les chaînes comprises dans une partie d'une autre chaîne.

Merci pour votre aide,
Laurent.

Le langage : Java ou SQL.