Levenstein Transpose Distance

Question

어떻게 동적 프로그래밍을 사용하여 조화/스왑/트위들/교환 거리 만 구현할 수 있습니까? 다른 작업 (예 : 복사, 삭제, 삽입, 삭제 등)을 확인하고 싶지는 않다는 점을 강조해야합니다.

Levenstein의 알고리즘을 스왑 거리에만 적용하고 싶습니다. 코드는 어떻게 생겼을까요?

Answer 1

이 경우 Levenstein의 알고리즘을 사용할 수 있는지 잘 모르겠습니다. 삽입 또는 삭제 작업을 수행하지 않으면 길이가 같고 문자가 같은 문자열 사이의 거리 만 정의됩니다. 그와

AB, ABC 
AAB, ABB 

이 알고리즘은 둘 문자열에 같은 장소에서 문자의 위치의 모든 가능한 순열을 찾을 수 있고 일을 찾습니다 수없는 문자열의 예는 트랜스 포지션과 동일한 문자열로 변환하기 최소 수의 전치 또는 스왑으로 나타낼 수 있습니다.

Answer 2

동적 프로그래밍을 효율적으로 적용하려면 일반적으로 작업을 더 짧은 입력을 위해 동일한 작업의 여러 인스턴스로 분해해야합니다. Levenstein 거리의 경우, 이것은 두 문자열의 접두어와 하나에서 다른 문자열로 이동하는 데 필요한 편집 횟수로 끝납니다. 나는 그런 분해가 당신의 경우 어떻게 달성 될 수 있는지 보지 못합니다. 적어도 나는 다항식 시간 알고리즘을 초래할 것이 보이지 않습니다.

또한 어떤 작업에 대해 이야기하고 있는지 분명하지 않습니다. 컨텍스트에 따라 스왑 또는 교환은 문자를 임의의 다른 문자로 바꾸거나 대체하는 것과 같은 것을 의미 할 수 있습니다. test->text. "transpose/swap/twiddle/exchange"로 "transpose"라고 말하면, Counting the adjacent swaps required to convert one permutation into another을 봐야합니다. 그렇지 않은 경우 질문을 명확히하십시오.