Petite question : l'interversion ne doit-elle concerner que des lettres consécutives ?
Quelle serait la distance de Hamming de "manger" et "ganmer" ?
1 pour une inversion, 2 pour deux lettres changées ? Voire 3 pour une inversion à une distance de 3 ?

Je pense que si c'est "2 pour deux lettres changées", on peut inclure un test simple dans un algorithme linéaire, mais sinon, on risque de devoir exécuter plusieurs algorithmes, pour gérer chaque cas...

Par exemple :
1 - algo qui calcule le solde au sens 1
2 - algo qui recherche les interversions, et qui enlève 1 pour chacune (et non pas qui rajoute ! Car une interversion a déjà été comptée deux fois dans le premier algo)
3 - ça, sincèrement, ça me parait compliqué à mettre en place ! Il faudrait voir ce qui est utilisé dans les algorithmes de <ital>diff</i> qui sont notamment intégrés aux outils de travail collaboratif (subversion, cvs...) Dans tous les cas, c'est à intégrer au 1er algorithme, sinon la distance explosera et il sera compliqué de la corriger.
4 - idem

l'interversion ne doit-elle concerner que des lettres consécutives ?

En principe oui.

Mais on devrait pouvoir calculer plusiers interversion consécutives:

manger
mganer
le g est décalé 2 fois vers la gauche ---> +2


on risque de devoir exécuter plusieurs algorithmes, pour gérer chaque cas...

C'est un peu ça qui m'inquiète, avec l'explosion combinatoire.

“Life is short - You need Python” -- Bruce Eckel, membre du comité ANSI C++

Le problème, c'est qu'arrivé à un certain niveau, j'ai peur qu'on se retrouve avec plusieurs distances pour deux chaines de caractères, puisque une modification peut-être obtenue par diverses combinaisons des différents critères... J'imagine que dans ce cas, on prend le min des distances... J'espère que tu ne veux pas calculer la distance de Hamming de deux romans, parce que là, ce serait vraiment ingérable à moins d'avoir un Cray à ta disposition ^^'

J'espère que tu ne veux pas calculer la distance de Hamming de deux romans

:-)

Non, heureusement.
“Life is short - You need Python” -- Bruce Eckel, membre du comité ANSI C++

Peut etre tu peux esseyer utiliser l'algorithme Wagner et Fischer.