최소 이동 수로 배열 정렬

Question

정렬 순서로 아직 정렬되지 않은 요소 만 이동하여 length(array) - length(longestIncreasingSubsequence(array)) 배열을 정렬 할 수 있습니다.

인덱스 A에서 요소를 제거하고 인덱스 B에 요소를 한 번에 하나씩 다시 삽입하면 정렬 된 배열로 끝나는 올바른 이동을 어떻게 생성 할 수 있습니까? 다시 말하지만, length(array) - length(longestIncreasingSubsequence(array)) 움직임이 필요합니다.

가

[ 1, 8, 5, 2, 4, 6, 3, 9, 7, 10 ] 

최장 증가 시퀀스이다 : 이러한 요소

[ 1, 2, 4, 6, 7, 10 ] 

인덱스들은 :

[ 0, 3, 4, 5, 8, 9 ] 

따라서 인덱스 예

여기 배열 인 우리는 이동해야합니다 :

[ 1, 2, 6, 7] 

이는 이미 정렬 된 순서가 아닌 색인이기 때문입니다. 정렬 된 어레이로 끝날 위해서는

, 그 4 개 요소의 최종 인덱스이다 :

[ 7, 4, 2, 8] 

그래서, 우리는 동시에 인덱스 4 인덱스 인덱스 7 인덱스 2 인덱스 1 이동해야 6을 인덱스 2에, 인덱스 7을 인덱스 8에 할당합니다. 문제는 요소가 이동 될 때 다른 요소가 이동되어 이후의 이동 작업이 무효화된다는 것입니다. 나는이 색인을 변형 시키려고 노력했지만, 지금까지 올바른 운동 목록을 찾지 못했습니다. 어떤 아이디어?

잘만 문제를 충분히 설명했습니다. 질문을하면 분명히 할 것입니다. 감사!

Answer 1

귀하의 문제는 소스 위치가 이전 순서대로 표시되고 목적지 위치가 최종 순위에있는 것입니다. 1-> 7을 할 때, 당신은 어디에서 7이 이전 순서인지 아직 알지 못합니다. 모든 동작을 조정해야합니다.

원래의 이동은 다음과 같습니다

from: [ 1, 2, 6, 7] 
to: [ 7, 4, 2, 8] 

1 단계

하자 최초의 tranform 우리는 다음 새 위치에 요소를 삽입, 먼저 모든 요소를 ​​제거하는 것처럼 위치를. from 위치의 경우 왼쪽에서부터 1 위치 이동 (2,6,7)에서 (1,5,6)까지 이동합니다. 1에서 다시 제거하면 (5,6)이 (4,5)로 이동합니다. 5시에 제거하면 5가 4로 이동합니다. from의 모든 위치에서 더 크거나 같은 색인이있는 모든 후속 위치를 감소시켜야합니다. 우리는 얻을 다음 to 위치에 대한

from: [ 1, 1, 4, 4] 

는 끝에서 진행 : 위치 8 맞습니다. 위치 2도 정확하지만 삽입시 이전 (7,4)이 실제로 (6,3) 였음을 의미합니다. 그래서 우리는 그들을 조정합니다. 유사하게, 3에서의 삽입은 이전 위치 6이 5임을 의미한다.

배열의 경우 to 배열의 경우 끝에서부터 모든 위치에 대해 색인이 큰 이전 위치를 모두 줄입니다. to 배열된다 :

to: [ 5, 3, 2, 8] 

2 단계

우리가 가진 것은 4 개 삽입 하였다 4 흡수량에 맞는 위치이다. 이제 제거 및 삽입을 인터리브하려고합니다.

(5, 5)는 (1, 1, 4)에서 제거하기 전에 수행해야합니다. 5는 이보다 더 크므로 위치 (1, 1, 4)에는 영향을 미치지 않지만 삽입 지점 왼쪽에서 3 회의 제거가 수행되므로 5가 영향을받습니다. 5는 8이됩니다.

(4, 4)에서 제거하기 전에 삽입해야합니다. 3이 4보다 작으므로 위치 3은 제거에 영향을받지 않지만 제거는 위치 (5, 5)로 증가해야합니다.

2에서의 삽입은 5시 마지막 제거 이전 (4 일 때)에옵니다.

for i = 0 to size-1 
    for j = size-1 to i+1 
     if from[j] < to[i] then increment to[i] 
     else increment from[j] 

우리는 배열을 얻어야한다 : 따라서 5 단계 2 6

일반적인 방법으로 조정, 작은이 함께 실행하는 최종 움직임이다

from: [ 1, 1, 5, 6] 
to: [ 8, 3, 2, 8] 

이동시 정확한 위치. 움직임은 왼쪽에서 오른쪽으로 읽을 수 있습니다 : 1에서 제거, 8에서 삽입. 1에서 제거, 3에서 삽입. 5에서 제거, 2에서 삽입. 6에서 제거, 8에서 삽입.