Lời giải dựa trên phép xoay

Để đơn giản, trước hết giả sử các mảng cần sắp không có phần tử lặp. Nếu có phần tử lặp, ta tùy ý chọn một thứ tự đúng giữa những phần tử bằng nhau.

Tạm bỏ qua giới hạn số hoán vị và dùng \(N-1\) hoán vị: hoán vị thứ \(i\) (\(1\le i\le N-1\)) đổi chỗ phần tử thứ \(i\) với phần tử thứ \(N\). Ví dụ, với \(N=5\), bốn hoán vị là:

5 2 3 4 1
1 5 3 4 2
1 2 5 4 3
1 2 3 5 4

Ta dùng phần tử thứ \(N\) làm “bộ đệm” để sắp \(N-1\) vị trí đầu:

1. Nếu phần tử ở vị trí \(N\) không phải lớn nhất, đổi nó tới đúng vị trí.
2. Nếu nó là lớn nhất, có hai trường hợp: mảng đã được sắp thì kết thúc; nếu chưa, đổi nó với bất kỳ phần tử nào đang ở sai vị trí để tiếp tục dùng làm bộ đệm.
3. Lặp lại từ bước 1.

Với mảng [30, 50, 40, 10, 20]:

1. Đưa 20 tới đúng vị trí: [30, 20, 40, 10, 50].
2. 50 đang ở cuối nhưng mảng chưa được sắp; đổi nó với một phần tử sai vị trí, chẳng hạn 30: [50, 20, 40, 10, 30].
3. Đưa 30 tới đúng chỗ: [50, 20, 30, 10, 40].
4. Đưa 40 tới đúng chỗ: [50, 20, 30, 40, 10].
5. Đưa 10 tới đúng chỗ: [10, 20, 30, 40, 50].

Lời giải này dùng \(N-1\) hoán vị và nhiều nhất \(1{,}5N\) thao tác đổi chỗ: \(N\) thao tác để đưa \(N\) phần tử vào đúng vị trí, cộng tối đa \(N/2\) lần dời phần tử thứ \(N\) khi nó là lớn nhất. Sau khi đổi phần tử lớn nhất với một phần tử sai vị trí, bước kế tiếp sẽ không cần làm việc đó lần nữa.

Giảm số hoán vị

Để đáp ứng giới hạn, thay vào đó dùng đúng năm phép:

• Một hoán vị đổi chỗ phần tử \(N-1\) và \(N\).
• Bốn hoán vị xoay mỗi phần tử từ 1 đến \(N-1\) lần lượt 1, 3, 9 và 27 vị trí; phần tử \(N\) giữ nguyên.

Khi \(N\le50\), bốn phép xoay này tạo được mọi độ xoay từ 1 tới \(N-2\) bằng không quá sáu thao tác. Chẳng hạn \(26=9+9+3+3+1+1\), còn \(47=27+9+9+1+1\). Tương đương, mọi số nhỏ hơn 50 biểu diễn được trong cơ số ba sao cho tổng các chữ số tam phân không quá 6; số nhỏ nhất cần ít nhất 7 phép là 53.

Thuật toán mới tương tự thuật toán dùng bộ đệm:

1. Nếu phần tử \(E\) ở vị trí \(N\) không phải lớn nhất, đưa nó tới đúng vị trí tương đối: xoay \(N-1\) phần tử đầu cho tới khi vị trí \(N-1\) là khe mà \(E\) cần vào, rồi đổi vị trí \(N-1\) và \(N\). \(E\) vào đúng chỗ, một phần tử khác đi vào bộ đệm.
2. Nếu \(E\) là phần tử lớn nhất, phải tạm dời nó khỏi vị trí \(N\). Chọn một phần tử chưa ở đúng vị trí tương đối trong \(N-1\) vị trí đầu và dùng cùng chiến lược xoay để đổi phần tử đó vào bộ đệm. Nếu có nhiều lựa chọn, chọn phần tử cần lượng xoay nhỏ nhất.
3. Lặp lại cho tới khi \(N-1\) phần tử đầu ở đúng thứ tự tương đối. Cuối cùng có thể cần thêm một số phép xoay để đưa chúng tới đúng vị trí tuyệt đối.

Với [30, 50, 40, 10, 20], chỉ cần ba hoán vị: đổi hai phần tử cuối 1 2 3 5 4; xoay bốn phần tử đầu 1 vị trí 4 1 2 3 5; và xoay chúng 3 vị trí 2 3 4 1 5.

• Muốn đặt 20 ngay sau 10: xoay 3 được [50, 40, 10, 30, 20], rồi đổi hai phần tử cuối được [50, 40, 10, 20, 30].
• Muốn đặt 30 ngay sau 20: xoay 3 được [40, 10, 20, 50, 30], rồi đổi hai phần tử cuối được [40, 10, 20, 30, 50].
• 50, phần tử lớn nhất, đang ở cuối. Phải đổi nó với một phần tử sai vị trí; ở đây chỉ có 40. Xoay 3 được [10, 20, 30, 40, 50], rồi đổi hai phần tử cuối được [10, 20, 30, 50, 40].
• Cuối cùng đổi hai phần tử cuối để đưa 40 về đúng chỗ: [10, 20, 30, 40, 50].

Số thao tác gồm \(1{,}5N\) lần đổi chỗ như thuật toán đầu, và \(6N\) phép xoay để đưa các phần tử vào đúng vị trí tương đối. Khi phần tử lớn nhất ở vị trí \(N\), cần thêm tổng cộng không quá \(N\) phép xoay: ta luôn chọn lượng xoay nhỏ nhất, rồi bước tiếp theo xoay mảng về cùng vị trí tương đối, nên tổng xoay của trường hợp này không quá một vòng đầy. Tổng cộng là \(8{,}5N\le425\) thao tác.

Một lời giải còn chặt hơn

Với mỗi \(N\le50\), tồn tại một tập bốn độ xoay cho phép xoay \(N-1\) phần tử đầu theo bất kỳ lượng nào từ 1 tới \(N-2\) trong không quá bốn thao tác, tận dụng việc xoay \(k\) tương đương xoay \(k+N-1\). Ví dụ với \(N=50\), tập \(\{1,3,12,20\}\) thỏa mãn. Khi đó trường hợp xấu nhất chỉ cần 325 thao tác.

Biến thể ngẫu nhiên

Một lời giải khác thay bốn phép xoay trên \(N-1\) phần tử bằng bốn đối hợp ngẫu nhiên, mỗi đối hợp đổi chỗ các cặp phần tử được chọn ngẫu nhiên.

Vẫn dùng thuật toán bộ đệm, nhưng để đưa đúng phần tử tới vị trí có thể đổi với bộ đệm, ta áp dụng một dãy các hoán vị ngẫu nhiên; sau phép đổi, áp dụng dãy đó theo thứ tự ngược để trả các phần tử còn lại về vị trí cũ. Có thể dùng BFS để tìm dãy ngắn nhất đưa một phần tử bất kỳ tới vị trí cần thiết.

Một tập hoán vị ngẫu nhiên có thể không giải được đầu vào hoặc cần quá nhiều thao tác, nhưng chỉ việc chọn lại bốn đối hợp khác. Xác suất tìm được lời giải dưới 450 thao tác là rất cao.

Nguồn

Dựa trên phân tích chính thức của Google Code Jam 2019, Chung kết thế giới, bài Sorting Permutation Unit; kho Google Coding Competitions (Apache-2.0).