Thuật toán để áp dụng hoán vị trong không gian bộ nhớ liên tục

Question

Tôi thấy câu hỏi này là một cuốn sách phỏng vấn lập trình, ở đây tôi đang đơn giản hóa câu hỏi.

Giả sử bạn có một mảng A chiều dài n, và bạn có một mảng hoán vị P chiều dài n là tốt. Phương thức của bạn sẽ trả về một mảng trong đó các phần tử của A sẽ xuất hiện theo thứ tự với các chỉ mục được chỉ định trong P.

Ví dụ nhanh: Phương pháp của bạn mất A = [a, b, c, d, e] và P = [4, 3, 2, 0, 1]. sau đó nó sẽ trả về [e, d, c, a, b]. Bạn chỉ được phép sử dụng không gian cố định (nghĩa là bạn không thể cấp phát một mảng khác, chiếm không gian O(n)).

Ý tưởng?

Answer 1

Có thuật toán O (n^2) tầm thường, nhưng bạn có thể thực hiện điều này trong O (n). Ví dụ:

A = [a, b, c, d, e]

P = [4, 3, 2, 0, 1]

Chúng ta có thể trao đổi mỗi phần tử trong A với quyền yếu tố theo yêu cầu của P, sau mỗi lần trao đổi, sẽ có yếu tố thêm một vào đúng vị trí, và làm điều này trong một hình tròn cho mỗi vị trí (yếu tố hoán đổi chỉ với ^ s):

[a, b, c, d, e] <- P[0] = 4 != 0 (where a initially was), swap 0 (where a is) with 4 
^   ^
[e, b, c, d, a] <- P[4] = 1 != 0 (where a initially was), swap 4 (where a is) with 1 
    ^ ^
[e, a, c, d, b] <- P[1] = 3 != 0 (where a initially was), swap 1 (where a is) with 3 
    ^ ^
[e, d, c, a, b] <- P[3] = 0 == 0 (where a initially was), finish step 

sau một vòng tròn, chúng tôi tìm thấy yếu tố tiếp theo trong mảng tha t không ở đúng vị trí, và làm điều này một lần nữa. Vì vậy, cuối cùng bạn sẽ nhận được kết quả mà bạn muốn, và vì mỗi vị trí được chạm vào một thời gian không đổi (đối với mỗi vị trí, tối đa một thao tác (hoán đổi) được thực hiện), nó là thời gian O (n).

Bạn có thể lưu trữ các thông tin trong đó một là ở đúng nơi của nó bằng cách:

1. thiết lập các mục tương ứng trong P là -1, đó là không thể phục hồi: sau khi các hoạt động trên, P sẽ trở thành [-1, -1, 2, -1, -1], biểu thị rằng chỉ cái thứ hai có thể không ở đúng vị trí, và một bước nữa sẽ đảm bảo nó ở đúng vị trí và kết thúc thuật toán;

2. đặt mục nhập tương ứng trong P thành -n - 1: P trở thành [-5, -4, 2, -1, -2], có thể được khôi phục trong O (n) trivially.

Answer 2

Do đó, bạn có thể đặt phần tử mong muốn vào trước mảng, trong khi làm việc với mảng còn lại có kích thước (n-1) trong bước lặp tiếp theo.

Mảng hoán vị cần được điều chỉnh tương ứng để phản ánh kích thước giảm của mảng. Cụ thể là, nếu phần tử bạn đặt ở mặt trước được tìm thấy ở vị trí "X", bạn cần giảm một chỉ số lớn hơn hoặc bằng X trong bảng hoán vị.

Trong trường hợp ví dụ của bạn:

array     permutation -> adjusted permutation 

A = {[a b c d e]}     [4 3 2 0 1] 
A1 = { e [a b c d]} [3 2 0 1] -> [3 2 0 1] (decrease all indexes >= 4) 
A2 = { e d [a b c]}  [2 0 1] ->  [2 0 1] (decrease all indexes >= 3) 
A3 = { e d c [a b]}  [0 1] ->  [0 1] (decrease all indexes >= 2) 
A4 = { e d c a [b]}   [1] ->   [0] (decrease all indexes >= 0) 

Một ví dụ khác:

A0 = {[a b c d e]}     [0 2 4 3 1] 
A1 = { a [b c d e]}  [2 4 3 1] -> [1 3 2 0] (decrease all indexes >= 0) 
A2 = { a c [b d e]}  [3 2 0] ->  [2 1 0] (decrease all indexes >= 2) 
A3 = { a c e [b d]}   [1 0] ->  [1 0] (decrease all indexes >= 2) 
A4 = { a c e d [b]}   [0] ->   [0] (decrease all indexes >= 1) 

Thuật toán, mặc dù không phải là nhanh nhất, tránh việc phân bổ bộ nhớ thêm trong khi vẫn giữ theo dõi những đơn hàng đầu tiên các yếu tố.

Answer 3

Chỉ là một ví dụ đơn giản C/C++ bổ sung mã vào câu trả lời của Ziyao Wei. Mã không được phép trong các ý kiến, như vậy là một câu trả lời, xin lỗi:

for (int i = 0; i < count;) 
{ 
    // Skip to the next non-processed item 
    if (destinations[i] < 0) 
     continue; 

    int currentPosition = i; 

    // destinations[X] = Y means "an item on position Y should be at position X" 
    // So we should move an item that is now at position X somewhere 
    // else - swap it with item on position Y. Then we have a right 
    // item on position X, but the original X-item now on position Y, 
    // maybe should be occupied by someone else (an item Z). So we 
    // check destinations[Y] = Z and move the X-item further until we got 
    // destinations[?] = X which mean that on position ? should be an item 
    // from position X - which is exactly the X-item we've been kicking 
    // around all this time. Loop closed. 
    // 
    // Each permutation has one or more such loops, they obvisouly 
    // don't intersect, so we may mark each processed position as such 
    // and once the loop is over go further down by an array from 
    // position X searching for a non-marked item to start a new loop. 
    while (destinations[currentPosition] != i) 
    { 
     const int target = destinations[currentPosition]; 

     std::swap(items[currentPosition], items[target]); 
     destinations[currentPosition] = -1 - target; 

     currentPosition = target; 
    } 

    destinations[currentPosition] = -1 - destinations[currentPosition]; 
} 

for (int i = 0; i < count; ++i) 
    destinations[i] = -1 - destinations[i]; 

(cho C - thay thế std :: swap với cái gì khác)

Answer 4

Tuy nhiên, một câu trả lời không cần thiết! Điều này bảo tồn mảng hoán vị P một cách rõ ràng, đó là cần thiết cho tình hình của tôi, nhưng hy sinh trong chi phí. Ngoài ra điều này không yêu cầu theo dõi các yếu tố được đặt chính xác. Tôi hiểu rằng câu trả lời trước đó cung cấp giải pháp O(N), vì vậy tôi đoán câu trả lời này chỉ để giải trí!

Chúng tôi nhận được trường hợp phức tạp tốt nhất O(N), trường hợp xấu nhất O(N^2) và trường hợp trung bình O(NlogN). Đối với mảng lớn (N~10000 hoặc cao hơn), trường hợp trung bình về cơ bản là O(N).

Đây là thuật toán cốt lõi trong Java (Ý tôi là pseudo-code * ho ho *)

int ind=0; 
float temp=0; 

for(int i=0; i<(n-1); i++){ 
    // get next index 
    ind = P[i]; 
    while(ind<i) 
    ind = P[ind]; 

    // swap elements in array 
    temp = A[i]; 
    A[i] = A[ind]; 
    A[ind] = temp; 
} 

Dưới đây là một ví dụ về thuật toán chạy (tương tự như câu trả lời trước):

cho A = [a, b, c, d, e]

và P = [2, 4, 3, 0, 1]

sau đó dự kiến ​​= [c, e, d, a, b]

i=0: [a, b, c, d, e] // (ind=P[0]=2)>=0 no while loop, swap A[0]<->A[2] 
    ^ ^
i=1: [c, b, a, d, e] // (ind=P[1]=4)>=1 no while loop, swap A[1]<->A[4] 
     ^ ^
i=2: [c, e, a, d, b] // (ind=P[2]=3)>=2 no while loop, swap A[2]<->A[3] 
      ^^ 
i=3a: [c, e, d, a, b] // (ind=P[3]=0)<3 uh-oh! enter while loop... 
       ^
i=3b: [c, e, d, a, b] // loop iteration: ind<-P[0]. now have (ind=2)<3 
     ?  ^
i=3c: [c, e, d, a, b] // loop iteration: ind<-P[2]. now have (ind=3)>=3 
      ?^
i=3d: [c, e, d, a, b] // good index found. Swap A[3]<->A[3] 
       ^
done. 

thuật toán này có thể trả lại xung quanh trong đó while vòng lặp cho bất kỳ chỉ số j<i, lên đến tối đa là i lần trong ith lặp. Trong trường hợp xấu nhất (tôi nghĩ!) Mỗi ​​lần lặp của vòng ngoài for sẽ dẫn đến việc thêm i các bài tập bổ sung từ vòng lặp while, vì vậy chúng tôi sẽ có một chuỗi số học đang diễn ra, sẽ thêm một yếu tố N^2 vào độ phức tạp! Chạy điều này trong phạm vi N và tính trung bình số lượng bài tập 'phụ' cần thiết theo vòng lặp while (trung bình trên nhiều hoán vị cho mỗi N, nghĩa là), mạnh mẽ cho tôi biết rằng trường hợp trung bình là O(NlogN).

Cảm ơn!

Answer 5

Giá trị trả lại cho ví dụ được đưa ra trong câu hỏi ban đầu là sai.

A = [a b c d e] 
P = [4 3 2 0 1] 

SHOULD return [d e c b a] not as as indicated in the question ([e d c a b])