Expressando uma permutação arbitrária como uma sequência de operações (inserir, mover, excluir)

9

Suponha que eu tenha duas cordas. Chamá-los de e . Nenhuma das cadeias possui caracteres repetidos.UMAB

Como posso encontrar a menor seqüência de operações de inserção, movimentação e exclusão que transforma em B , onde:UMAB

  • insert(char, offset)insere charno dado offsetna string
  • move(from_offset, to_offset)move o personagem atualmente em deslocamento from_offsetpara uma nova posição para que ele tenha deslocamentoto_offset
  • delete(offset) exclui o caractere em offset

Exemplo de aplicativo: você faz uma consulta ao banco de dados e mostra os resultados no seu site. Mais tarde, execute novamente a consulta do banco de dados e descubra que os resultados foram alterados. Você deseja alterar o que está na página para corresponder ao que está atualmente no banco de dados usando o número mínimo de operações DOM. Há duas razões pelas quais você deseja a menor sequência de operações. Primeiro, eficiência. Quando apenas alguns registros são alterados, você deseja certificar-se de executar operações vez de DOM, pois elas são caras. Segundo, correção. Se um item for movido de uma posição para outra, você deseja mover os nós DOM associados em uma única operação, sem destruí-los e recriá-los. Caso contrário, você perderá o estado de foco, o conteúdo deO(1 1)O(n)<input> elementos e assim por diante.

Geoff
fonte

Respostas:

10

Sugiro dar uma olhada no algoritmo de distância de edição . Em vez de apenas calcular a distância, registre seu caminho de peso mínimo através da matriz e retorne-o.

Rick Minerich
fonte
5
De fato, como não há repetições, esse é um problema um pouco mais simples chamado problema de distância de Ulam. Embora você possa usar o algoritmo de edição de distância, também existem métodos mais rápidos direcionados para essa distância: mit.edu/~andoni/papers/ulamSublinear.pdf
Suresh
11
A distância de edição geralmente não abrange moveoperações, portanto, pode ser necessário variar ao interpretar a pontuação.
Raphael