Maximum de différences

Signaler
Messages postés
41
Date d'inscription
mardi 30 septembre 2003
Statut
Membre
Dernière intervention
21 avril 2011
-
Messages postés
41
Date d'inscription
mardi 30 septembre 2003
Statut
Membre
Dernière intervention
21 avril 2011
-
Bonjour,
Je butte sur un problème qui semble simple mais qui ne l'est pas tant que ça.
J'ai un tableau non rectangulaire:
ex:
[i]a b c
d e
f g h i
j k l
m n o p q/i
... et je voudrai obtenir les 5 chaînes de caratère les plus différentes ( qui ont le moins de caractères identiques).
J'ai bien sûr déjà essayé de trouver toutes les combinaisons(fonction récursive et itérative) puis de classer les résultats mais les ressources nécessaires sont trop importantes quand le tableau est grand.
Quelqu'un connaît-il la solution de ce casse-tête?

Merci.

2 réponses

Messages postés
1540
Date d'inscription
lundi 26 mai 2003
Statut
Membre
Dernière intervention
1 août 2013
12
Salut,

la difficulté et la complexité viennent surtout de la fonction de calcul de la "différence", un parcours de tableau reste un parcours de tableau. La seule astuce serait de t'arrêter après avoir trouver 5 chaînes avec aucune lettre identique.

D'ailleurs, comment calcule-tu cette "différence" ? ça m'intrigue

PS : sur du calcul très lourd il faut éviter le récursif ;)
Messages postés
41
Date d'inscription
mardi 30 septembre 2003
Statut
Membre
Dernière intervention
21 avril 2011

Merci de vous intéresser à mon problème.
Le calcul des différences se fait ainsi:
ex:
a b c
d e
f g h i
j k l
m n o p q

soit la série 1: a d f j m
puis la série 2: b e g k n à 100% de différence.
puis la série 3: c d h l o à 100% de diff avec série 2 mais 80% avec 1 donc je garde cette valeur (la plus faible)

je prend une serie au hasard puis je l'ajoute à un nouveau tableau et je compare chaque élément de chaque série du premier tableau avec chaque élément de chaque série du nouveau tableau et j'ajoute la série au nouveau tableau si c'est celui qui a le plus différences. Ainsi j'obtiens des séries rangées par ordre croissant de différences relatives mais c'est très long.

Pour avoir des chaînes avec aucune lettre identique: il me suffit de prendre le tableau colonne par colonne. ce n'est pas un problème. Mais le problème vient lorsque certaine lettres sont présente dans d'autre chaînes.

J'ai bien sûr suprimées les méthodes récursives et les ai remplacées par des méthodes itératives dès que j'ai vue les problème lors de l'execution.

Merci.