Supposons qu'il soit donné à deux chaînes:
String s1= "MARTHA" String s2= "MARHTA"
3 Réponses :
Il y a plusieurs Distance d'édition algorithmes, la liaison Wikipeida donnée a des liens vers quelques-uns. < / p>
Aucun de ceux qui ne prennent que des swaps en considération.
Votre problème n'est pas si facile, car avant de compter les swaps, vous devez vous assurer que chaque swap réduit la "distance" (dans l'égalité) entre ces deux chaînes. Ensuite, vous recherchez le comte mais vous devriez rechercher le plus petit nombre (ou au moins je suppose), sinon il existe des moyens infinis d'échanger une chaîne pour en obtenir un autre.
Vous devez d'abord vérifier quels chariots sont déjà en place, puis pour chaque personnage qui n'est pas regardé s'il y a un couple qui peut être échangé de manière à ce que la prochaine distance entre les chaînes soit réduite. Ensuite, itérez jusqu'à la fin du processus.
Si vous ne voulez pas le faire efficacement, il suffit de compter le nombre de swaps utilisez un tableau de bits dans lequel vous avez 1 pour chaque caractère bien placé et 0 sinon. Vous finirez quand chaque bit est 1 .
Et cela garantit le nombre minimum de swaps comment? Vous pourriez vous retrouver dans une boucle infinie si vous échangez aveuglément des éléments, ou du moins dans une impasse qui ne finit pas la conversion de la chaîne.
La contrainte d'itération est de réduire la distance entre les cordes. Comment pouvez-vous vous retrouver dans une boucle infinie si vous vous assurez que chaque étape réduit la distance? Il peut rester coincé, assurant que les deux chaînes ne sont pas «échangez égal», mais cela garantit de ne pas boucle sans rien faire. L'approche s'appelle gourmand qui garantit que, si une optimum locale est conservée (en réduisant la distance annonce chaque itération), l'optimum global est une conséquence directe.
Ensuite, je suppose que nous parlons de swaps de deux éléments i et j où il n'y a pas de contraintes telles que i = j + 1 ou vice versa. En outre, parce que l'OP n'a pas dit des swaps adjacents, mais il suffit de swaps ..
Oui, cela s'appelle gourmand, et vous devez prouver que vos travaux gourmands, car les algorithmes gourmands ne fonctionnent généralement que pour un type de problèmes très étroit et spécifique. Vous ne finirez pas dans une boucle infinie, mais vous risquez d'être bloqué lorsque les deux sont effectivement «échangez égal» et sinon vous ne trouverez peut-être pas la meilleure solution. Fondamentalement, vous devez prouver que votre algorithme est correct.
Comme je l'ai signalé dans ma réponse, si nous supposons qu'il n'y a pas de chiffres répétés, cela peut être résolu en temps linéaire. J'aimerais entendre vos opinions sur la manière dont je peux l'améliorer pour couvrir le cas de lettres non uniques également.
En supposant que la distance compte uniquement les swaps, voici une idée basée sur des permutations, qui fonctionne en temps linéaire.
La première étape de l'algorithme consiste à garantir que les deux chaînes sont vraiment équivalentes dans leur contenu de caractère. Cela peut être fait en temps linéaire à l'aide d'une table de hachage (ou d'une matrice fixe qui couvre tout l'alphabet). S'ils ne le sont pas, alors S2 ne peut pas être considéré comme une permutation de S1, et le «nombre d'échange» n'est pas pertinent.
La deuxième étape compte le nombre minimum de swaps nécessaires pour transformer S2 en S1. Cela peut être fait en inspectant la permutation P qui correspond à la transformation de S1 en S2. Par exemple, si S1 = "ABCDE" et S2 = "Badce", p = (2,1,4,3,5), ce qui signifie que la position 1 contient l'élément n ° 2, la position 2 contient l'élément n ° 1, etc. La permutation peut être rompue dans Cycles de permutation en temps linéaire. Les cycles dans l'exemple sont (2,1) (4,3) et (5). Le nombre de swap minimum est le nombre total de swaps requis par cycle. Un cycle de longueur K nécessite des swaps K-1 afin de "résoudre". Par conséquent, le nombre de swaps est N-C, où n est la longueur de la chaîne et c est le nombre de cycles. Dans notre exemple, le résultat est 2 (swap 1,2 puis 3,4).
Maintenant, il y a deux problèmes ici, et je pense que je suis trop fatigué pour les résoudre en ce moment :)
1) Ma solution suppose qu'aucun caractère n'est répété, ce qui n'est pas toujours le cas. Un certain ajustement est nécessaire pour calculer correctement le nombre de swaps.
2) Ma formule # Minwaps = N-C a besoin d'une preuve ... Je ne l'ai pas trouvé dans le Web.
Oh wow, 110 questions, 3 réponses et seulement 6 upvotes?