Exprimer une permutation arbitraire comme une séquence d'opérations (insérer, déplacer, supprimer)

9

Supposons que j'ai deux chaînes. Appelez - les et . Aucune chaîne n'a de caractères répétés.AB

Comment puis-je trouver la séquence la plus courte d'opérations d'insertion, de déplacement et de suppression qui transforme en , où:BUNEB

  • insert(char, offset)insère charau donné offsetdans la chaîne
  • move(from_offset, to_offset)déplace le caractère actuellement décalé from_offsetvers une nouvelle position afin qu'il soit décaléto_offset
  • delete(offset) supprime le caractère à offset

Exemple d'application: vous effectuez une requête dans la base de données et affichez les résultats sur votre site Web. Plus tard, vous réexécutez la requête de base de données et découvrez que les résultats ont changé. Vous souhaitez modifier ce qui se trouve sur la page pour correspondre à ce qui se trouve actuellement dans la base de données en utilisant le nombre minimum d'opérations DOM. Il y a deux raisons pour lesquelles vous souhaiteriez la séquence d'opérations la plus courte. Tout d'abord, l'efficacité. Lorsque seuls quelques enregistrements changent, vous devez vous assurer que vous effectuez les opérations DOM plutôt que , car elles sont coûteuses. Deuxièmement, l'exactitude. Si un élément est déplacé d'une position à une autre, vous souhaitez déplacer les nœuds DOM associés en une seule opération, sans les détruire ni les recréer. Sinon, vous perdrez l'état de la mise au point, le contenu des éléments, etc.O ( n )O(1)O(n)<input>

Geoff
la source

Réponses:

10

Je suggère de jeter un œil à l' algorithme de modification de la distance . Au lieu de simplement calculer la distance, vous voudrez enregistrer votre chemin de poids minimum à travers le tableau et le retourner.

Rick Minerich
la source
5
En fait, puisqu'il n'y a pas de répétitions, il s'agit d'un problème légèrement plus simple appelé problème de distance Ulam. Bien que vous puissiez utiliser l'algorithme d'édition de distance, il existe également des méthodes plus rapides ciblées sur cette distance: mit.edu/~andoni/papers/ulamSublinear.pdf
Suresh
1
La distance d'édition ne couvre généralement pas les moveopérations, vous devrez donc peut-être varier lors de l'interprétation de la partition.
Raphael