문자열 전치 알고리즘은

Question

는이 주어진 것으로 가정 해 보겠습니다 두 개의 문자열 : 여기 우리는 T와 H. 나는 많은 변화가 다른 문자열 하나의 문자열로 변환하는 데 필요한 방법을 계산하는 코드를 작성하는 것이 관심의 위치를 ​​교환

String s1= "MARTHA" 
String s2= "MARHTA" 

.

Answer 1

거리 계산이 스왑 일 뿐이라고 가정하면 순열을 기반으로 한 아이디어가 선형 시간으로 실행됩니다.

알고리즘의 첫 번째 단계는 두 문자열이 문자 내용에서 실제로 동등한 지 확인하는 것입니다. 해시 테이블 (또는 모든 알파벳을 포함하는 고정 배열)을 사용하여 선형 시간으로 수행 할 수 있습니다. 그렇지 않은 경우 s2는 s1의 순열로 간주 될 수 없으며 "스왑 카운트"는 부적합합니다.

두 번째 단계는 s2를 s1로 변환하는 데 필요한 최소 스왑 수를 계산합니다. 이것은 s1에서 s2 로의 변환에 해당하는 순열 p를 검사함으로써 수행 될 수있다. 예를 들어, s1 = "abcde"및 s2 = "badce"이면 p = (2,1,4,3,5)입니다. 즉 위치 1에는 요소 2가 포함되고 위치 2에는 요소 1이 포함됩니다. 순열은 선형 시간으로 permutation cycles으로 분해 될 수있다. 예제의주기는 (2,1) (4,3) 및 (5)입니다. 최소 스왑 카운트는 사이클 당 필요한 스왑의 총 카운트입니다. 길이 k의 사이클은 k-1 스왑을 필요로하여 "고쳐야"합니다. 따라서 스왑의 수는 N-C이며 N은 문자열 길이이고 C는 사이클 수입니다. 위의 예에서 결과는 2 (스왑 1,2와 3,4)입니다.

지금, 두 가지 문제가 여기에있다, 그리고 나는 지금 그들을 해결하기 위해 너무 피곤 해요 :)

1) 내 솔루션은 어떤 문자가 항상 그런 것은하지 않은, 반복되지 않는 것으로 가정합니다 생각합니다. 스왑 카운트를 올바르게 계산하려면 약간의 조정이 필요합니다.

2) 내 수식 # MinSwaps = N-C는 증명이 필요합니다. 웹에서 찾지 못했습니다.

Answer 2

edit distance 알고리즘이 여러 개 있습니다. 주어진 Wikipeida 링크에는 몇 개의 링크가 있습니다.

Answer 3

스왑을 계산하기 전에 모든 스왑이이 두 문자열 사이의 "거리"(평등하게)를 줄 이도록해야하기 때문에 문제가 쉽지 않습니다. 그렇다면 사실 당신은 카운트를 찾는다. 그러나 가장 작은 카운트 (또는 적어도 나는 생각한다)를 찾아야한다. 그렇지 않으면 문자열을 다른 것으로 바꾸기위한 무한한 방법이있다.

먼저 문자가 자리에있는 문자를 확인한 다음, 문자 사이의 다음 거리가 줄어들도록 교체 할 수있는 쌍이 있는지 없는지 확인하십시오. 그런 다음 프로세스를 마칠 때까지 반복합니다.

효과적으로 수행하고 싶지는 않지만 스왑의 수를 계산하려면 잘 배치 된 모든 문자에 대해 1이고 그렇지 않은 경우에는 0 인 비트 배열을 사용하십시오. 모든 비트가 1 일 때 완료됩니다.