순열을 순차적으로 찾는 알고리즘

Question

간단한 문제를 묻습니다 : 복잡도가 가장 낮은 순차 (반복)를 사용하여 하나의 순열을 찾는 방법은 무엇입니까?

시퀀스가 ​​1 1 2 3 4 인 것으로 가정합니다. 그런 다음 2와 3을 치환하므로 1 1 3 2 4이됩니다. 2와 3이 치환되었음을 어떻게 알 수 있습니까? 최악의 해결책은 모든 가능성을 생성하고 원래의 치환 순서와 각각을 비교하는 것이지만, 나는 빠른 것을 필요로합니다 ...

답장을 보내 주셔서 감사합니다.

Answer 1

function findswaps: 
    linkedlist old <- store old string in linkedlist 
    linkedlist new <- store new string in linkedlist 

    compare elements one by one: 
     if same 
      next iteration until exhausted 
     else 
      remember old item 
      iterate through future `new` elements one by one: 
       if old item is found 
        report its position in new list 
       else 
        error 

제 겸손한 시도는 잘못하면 저를 교정하십시오. 그래서 도움이 될 수 있습니다. 데이터가 정렬되지 않은 것 같아 선형보다 더 빠를 수 없습니까?

Answer 2

문제는 순서가 순차적으로 발견되는 등 몇 가지 제약없이 문제에 대한 여러 가지 해결책이 있다는 것입니다.

내가봤을 때 첫 번째 테스트는 시퀀스에 여전히 동일한 값이 있고 하나의 불일치가 발견 될 때까지 단계별로 진행 한 다음 다른 값의 첫 번째 발생 위치와 그것을 순열로 표시하십시오. 이제 다음 수정 작업을 계속 진행하십시오.

변경된 사항을 알고 싶다면 levenshtein 알고리즘을 살펴 보겠습니다. 이 알고리즘의 기본은 사용자 정의 알고리즘에 필요한 것을 제공하거나 다른 접근 방법에 영감을 줄 수 있습니다.

이것은 빠르지 만 변경된 항목을 알려주지 않습니다.

제가 알고있는 유일한 해결책은 각 변경 사항을 기록하는 것입니다. 그러면 변경 사항의 기록을보고 완벽한 답변을 알 수 있습니다.

Answer 3

원본과 파생 배열 사이에만 1 스왑이 있다면, 당신은 배열의 길이 n에 대한 O (N)에서 같은 것을 시도해 볼 수도 있습니다 :이 아무것도 교환되지 않은 경우 실패보고하는

int count = 0; 
int[] mismatches; 

foreach index in array { 
    if original[index] != derived[index] { 
     if count == 2 { 
      fail 
     } 
     mismatches[count++] = index; 
    } 
} 

if count == 2 and 
    original[mismatches[0]] == derived[mismatches[1]] and 
     original[mismatches[1]] == derived[mismatches[0]] { 

    succeed 
} 

fail 

주 배열 사이.