On procède par tri par insertion.
Cet algorithme est de complexité [latex]O(n^2)[/latex] en moyenne donc je vote pour une réponse proche de [latex]37^2=1369[/latex]

EDIT : Après application je trouve [latex]187[/latex]

Il faut procéder à 151 échanges.

Comment y arriver?

Etape 0: Prendre E=0, n=1;
Etape 1: Prendre le nième chiffre de b, notons ce chiffre x;
Etape 2: Compter le nombre de chiffres avant la première apparition de x dans a (notons ce nombre k),
Etape 3: Ajouter k à E;
Etape 4: Supprimer x de a;
Etape 5: Augmenter n d'une unité;
Etape 6: Si b est vide alors E est le nombre d'échanges, sinon retourner à l'étape 1.

Ma méthode résout le problème, mais est ce le nombre minimum? Je ne saurai l'affirmer.

.

Bonjour, supposons dans un premier temps que tout les chiffres soient distants.
Prenons l'exemple 946375182->123456789
On compte le nombre de chiffres supérieurs à un chiffre donné situé à sa droite, et ce pour chaque chiffres.
Ici, 1 va devoir passer au dessus de 946375, 2 au dessus de 9463758
3 va devoir passer au dessus 946
4 va devoir passer au dessus de 9
5 va devoir passer au dessus de 967
...
On obtient au final un certain nombre n de chiffres à "passer"
Chaque transposition augmente ou diminue n de 1:
Si on passe un grand au dessus d'un petit (79->97), la valeur de 7 augmente de un, mais pas celle de 9.
Inversement, un petit au dessus d'un grand diminue la valeur de 1.
Si l'on procède dans l'ordre (placer le 1, puis le 2...), la valeur de n diminue de 1 à chaque fois (le 1 ne peut passer qu'au dessus de valeurs plus grandes, le 2 aussi, à part 1, mais il est déjà au bout, et ainsi de suite)

Si l'on place les chiffres l'un après l'autre, il n'y a pas de mouvements supplémentaires, chaque mouvement "trie" le nombre, c'est le principe du tri par insertion.

Dans le cas où les chiffres peuvent être identiques, il faut associer chaque chiffre à un chiffre unique, deux chiffres identiques mais à deux endroits différents du mot étant associer à un nouveau chiffre distinct l'un de l'autre. On peut alors appliquer notre procédé précédent.
Il faut donc trouver quel "étiquetage" donne une valeur de n la plus petite possible. La réponse est intuitive, il suffit de le faire dans l'ordre:
Par exemple, pour 1232143 -> 1122334
On ré-étiquette le deuxième nombre 1234567.
Le premier sera donc étiqueté 1354276.
On voit bien que proposer un autre étiquetage donnera une valeur de n plus élevée, car pour toutes les instances du chiffre k, le chiffre k ne sautera que pour les valeurs strictement inférieures à k dans le cas proposé ici, mais devra sauter au dessus de valeurs égales à k dans les autres cas. (A noter que changer l'étiquetage entre les valeurs de k ne change pas les valeur associées aux autres chiffres)

Application:
Dans notre, si on étiquette le deuxième nombre 1|2|3|...|37, on trouve pour le premier la permutation 14|3|18|17|6|9|8|1|21|2|5|4|12|19|11|26|10|20|34|13|23|7|32|15|24|22|33|25|28|16|36|30|27|37|29|31|35.
La somme des sauts donne:
1+1+3+3+4+7+8+7+8+4+1+6+8+2+8+2+15+1+9+3+5+1+4+3+14+4+6+6+5+2=151 ce qui nous donne 151 transpositions à effectuer afin de modifier notre nombre (sauf erreur de calcul)

@ tous : il existe une preuve assez expéditive, comme les aime Vasimolo, qui montre qu'on ne peut pas faire moins d'échanges que le nécessaire.