Giả sử A = (3,7,5,4) là một hoán vị hiện tại của tập {3,5,7,4}, bộ nào sau đây là hoán vị tiếp theo của hoán vị A trong thuật toán liệt kê hoán vị bằng phương pháp sinh.
Trả lời:
Đáp án đúng: A
Thuật toán sinh hoán vị kế tiếp hoạt động như sau:
1. **Tìm phần tử a[k] từ cuối dãy lên:** Tìm từ cuối dãy lên phần tử a[k] sao cho a[k] < a[k+1]. Nếu không tìm thấy, đây là hoán vị cuối cùng.
2. **Tìm phần tử a[l] từ cuối dãy lên:** Tìm từ cuối dãy lên phần tử a[l] sao cho a[l] > a[k].
3. **Đổi chỗ a[k] và a[l]:** Đổi chỗ hai phần tử này.
4. **Đảo ngược đoạn từ k+1 đến cuối dãy:** Đảo ngược thứ tự các phần tử từ vị trí k+1 đến cuối dãy.
Áp dụng vào ví dụ A = (3, 7, 5, 4):
* Bước 1: Tìm a[k]. Ta thấy 5 < 4 là sai, 7 < 5 là sai, 3 < 7 là đúng. Vậy k = 1 và a[k] = 3.
* Bước 2: Tìm a[l]. Ta thấy 4 > 3 là đúng, 5 > 3 là đúng, 7 > 3 là đúng. Vậy l = 3 và a[l] = 4.
* Bước 3: Đổi chỗ a[k] và a[l]: A trở thành (4, 7, 5, 3).
* Bước 4: Đảo ngược đoạn từ k+1 đến cuối dãy: Đảo ngược (7, 5, 3) thành (3, 5, 7). Vậy A trở thành (3, 4, 5, 7).
Vậy hoán vị tiếp theo của (3, 7, 5, 4) là (3, 4, 5, 7).
