Sắp xếp mảng theo số lần di chuyển tối thiểu

Question

Về mặt lý thuyết có thể sắp xếp một mảng theo kiểu length(array) - length(longestIncreasingSubsequence(array)) di chuyển bằng cách chỉ di chuyển các phần tử chưa có thứ tự sắp xếp.

Nếu thao tác duy nhất được phép là di chuyển tại chỗ, bằng cách xóa phần tử khỏi chỉ mục A và chèn lại thành chỉ mục B, một phần tử tại một thời điểm, bạn sẽ tạo ra các bước chính xác để kết thúc với mảng được sắp xếp như thế nào? Một lần nữa, cần có yêu cầu di chuyển length(array) - length(longestIncreasingSubsequence(array)).

Ví dụ, đây là một mảng:

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

Các dãy con tăng dài nhất là:

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

Các chỉ số của những yếu tố này là:

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

Vì vậy, các chỉ số chúng tôi cần di chuyển là:

[ 1, 2, 6, 7] 

vì đó là các chỉ mục chưa có thứ tự sắp xếp.

Để kết thúc với một mảng được sắp xếp, các chỉ số cuối cùng của những 4 yếu tố là:

[ 7, 4, 2, 8] 

Vì vậy, chúng ta cần phải đồng thời di chuyển chỉ số từ 1 tới chỉ số 7, chỉ số 2 đến số 4, chỉ số 6 đến chỉ mục 2 và chỉ mục 7 đến chỉ mục 8. Vấn đề là khi một phần tử được di chuyển, các phần tử khác được dịch chuyển xung quanh làm cho các hoạt động di chuyển sau này không hợp lệ. Tôi đã thử chuyển đổi các chỉ mục này, nhưng cho đến nay vẫn chưa có danh sách đúng các bước di chuyển cần thiết. Bất kỳ ý tưởng?

Hy vọng rằng tôi đã giải thích được vấn đề đủ tốt. Vui lòng đặt câu hỏi và tôi sẽ làm rõ. Cảm ơn!

Answer 1

Vấn đề của bạn là vị trí nguồn được thể hiện theo thứ tự trước trong khi các vị trí đích nằm trong thứ tự cuối cùng. Khi bạn thực hiện 1-> 7, bạn vẫn chưa biết vị trí thứ 7 nằm trong thứ tự trước. Bạn cần phải thực hiện điều chỉnh cho tất cả các di chuyển.

Động thái ban đầu là:

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

Bước 1

Hãy tranform đầu tiên các vị trí như thể chúng tôi đã loại bỏ tất cả các yếu tố đầu tiên, sau đó chèn các yếu tố tại các vị trí mới. Đối với các vị trí from, tiến hành từ bên trái: xóa tại 1 vị trí thay đổi (2,6,7) xuống tới (1,5,6). Loại bỏ tại 1 lần nữa (5,6) xuống còn (4,5). Loại bỏ tại 5 thay đổi 5 xuống 4. Đối với mỗi vị trí trong from tất cả các vị trí tiếp theo có chỉ số lớn hơn hoặc bằng nhau phải được giảm đi. Chúng tôi nhận được:

from: [ 1, 1, 4, 4] 

Đối với các vị trí to, tiến hành từ đầu: Vị trí 8 là chính xác. Vị trí 2 cũng đúng, nhưng nó có nghĩa là trước đó (7,4) đã thực sự (6,3) tại thời điểm chèn. Vì vậy, chúng tôi điều chỉnh chúng. Tương tự như vậy, chèn tại 3 có nghĩa là vị trí trước 6 là 5.

Vì vậy, đối với mảng to, chúng tôi tiến hành từ cuối, cho mọi vị trí chúng tôi giảm tất cả các vị trí trước có chỉ số lớn hơn. Mảng to trở thành:

to: [ 5, 3, 2, 8] 

Bước 2

Những gì chúng ta có là vị trí chính xác cho 4 ñuoåi theo sau là 4 chèn. Bây giờ chúng tôi muốn xen kẽ các loại bỏ và chèn.

Việc chèn tại 5 phải được thực hiện trước khi xóa tại (1, 1, 4). 5 là lớn hơn bất kỳ trong số này, do đó, nó sẽ không ảnh hưởng đến các vị trí (1, 1, 4), nhưng 5 bị ảnh hưởng bởi vì 3 ñuoå ñöôïc ñöôïc ñöôïc ñöôïc ñöôïc ñöôïc ñöôïc ñöôïc ñöôïc ñöôïc ñöôïc. 5 trở thành 8.

Chèn tại 3 phải đến trước khi xóa tại (4, 4). Vì 3 nhỏ hơn số 4, vị trí 3 không bị ảnh hưởng bởi việc xóa bỏ, nhưng việc xóa bỏ phải được tăng lên, đến các vị trí (5, 5).

Chèn tại 2 đến trước lần xóa cuối cùng ở mức 5 (là 4). Nó là nhỏ hơn, do đó 5 được điều chỉnh 6.

phương pháp chung cho bước 2:

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] 

Chúng tôi sẽ nhận được các mảng:

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

Đây là những động thái cuối cùng để thực hiện với các vị trí chính xác tại thời điểm di chuyển. Các di chuyển có thể được đọc từ trái sang phải: Loại bỏ tại 1, chèn tại 8. Hủy bỏ tại 1, chèn tại 3. Hủy bỏ tại 5, chèn tại 2. Hủy bỏ tại 6, chèn tại 8.