Bài toán hoán vị

Bài toán hoán vị là một ứng dụng kinh điển của thuật toán quay lui. Nó được định nghĩa là việc tìm tất cả các cách sắp xếp có thể có của các phần tử trong một tập hợp cho trước (chẳng hạn như một mảng hoặc một chuỗi).

Bảng dưới đây hiển thị một số tập dữ liệu ví dụ, bao gồm mảng đầu vào và các hoán vị tương ứng của chúng.

Bảng   Các ví dụ hoán vị

Mảng đầu vào	Tất cả các hoán vị
\([1]\)	\([1]\)
\([1, 2]\)	\([1, 2], [2, 1]\)
\([1, 2, 3]\)	\([1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]\)

Trường hợp các phần tử phân biệt

Question

Cho một mảng số nguyên không chứa các phần tử trùng lặp, hãy trả về tất cả các hoán vị có thể có.

Dưới góc độ của thuật toán quay lui, chúng ta có thể hình dung quá trình tạo ra các hoán vị như kết quả của một chuỗi các lựa chọn. Giả sử mảng đầu vào là \([1, 2, 3]\). Nếu đầu tiên chúng ta chọn \(1\), tiếp theo chọn \(3\), và cuối cùng chọn \(2\), chúng ta sẽ thu được hoán vị \([1, 3, 2]\). Quay lui có nghĩa là hoàn tác một lựa chọn và sau đó thử các lựa chọn khác.

Dưới góc độ của mã nguồn quay lui, tập hợp ứng viên choices bao gồm tất cả các phần tử trong mảng đầu vào, và trạng thái state là các phần tử đã được chọn cho đến hiện tại. Lưu ý rằng mỗi phần tử chỉ có thể được chọn một lần, do đó tất cả các phần tử trong state phải là duy nhất.

Như được hiển thị trong hình dưới đây, chúng ta có thể triển khai quá trình tìm kiếm thành một cây đệ quy, trong đó mỗi nút trong cây đại diện cho trạng thái hiện tại state. Bắt đầu từ nút gốc, sau ba vòng lựa chọn, chúng ta đạt đến một nút lá, và mỗi nút lá tương ứng với một hoán vị.

Cắt tỉa các lựa chọn trùng lặp

Để đảm bảo mỗi phần tử chỉ được chọn một lần, chúng ta cân nhắc giới thiệu một mảng boolean selected, trong đó selected[i] cho biết liệu choices[i] đã được chọn hay chưa. Chúng ta thực hiện thao tác cắt tỉa sau dựa trên nó.

• Sau khi thực hiện một lựa chọn choices[i], chúng ta đặt selected[i] thành \(\text{True}\), cho biết nó đã được chọn.
• Khi duyệt qua danh sách ứng viên choices, chúng ta bỏ qua tất cả các nút đã được chọn, đây chính là cắt tỉa.

Như thể hiện trong hình dưới đây, giả sử chúng ta chọn \(1\) ở vòng đầu tiên, chọn \(3\) ở vòng thứ hai, và chọn \(2\) ở vòng thứ ba. Khi đó chúng ta cần cắt tỉa nhánh của phần tử \(1\) ở vòng thứ hai và cắt tỉa các nhánh của các phần tử \(1\) và \(3\) ở vòng thứ ba.

Quan sát hình trên, chúng ta thấy rằng thao tác cắt tỉa này làm giảm kích thước không gian tìm kiếm từ \(O(n^n)\) xuống \(O(n!)\).

Cài đặt mã nguồn

Sau khi đã hiểu các thông tin trên, chúng ta có thể điền vào các chỗ trống trong khung mã nguồn mẫu. Để rút gọn tổng thể mã nguồn, chúng ta không hiện thực riêng biệt từng hàm trong khuôn mẫu, mà triển khai trực tiếp chúng trong hàm backtrack():

[file]{permutations_i}-[class]{}-[func]{permutations_i}

Trường hợp chứa phần tử trùng lặp

Question

Cho một mảng số nguyên có thể chứa các phần tử trùng lặp, hãy trả về tất cả các hoán vị duy nhất.

Giả sử mảng đầu vào là \([1, 1, 2]\). Để phân biệt hai phần tử trùng lặp \(1\), chúng ta ký hiệu phần tử \(1\) thứ hai là \(\hat{1}\).

Như được hiển thị trong hình dưới đây, một nửa số hoán vị được tạo ra bởi phương pháp trên là trùng lặp.

Vậy làm thế nào để loại bỏ các hoán vị trùng lặp? Cách tiếp cận trực tiếp nhất là sử dụng một tập hợp băm (hash set) để trực tiếp loại bỏ các phần tử trùng lặp trong kết quả hoán vị. Tuy nhiên, điều này không tinh tế bởi vì các nhánh tìm kiếm tạo ra các hoán vị trùng lặp là không cần thiết và nên được nhận diện và cắt tỉa sớm, điều này có thể nâng cao hơn nữa hiệu suất của thuật toán.

Cắt tỉa các phần tử bằng nhau

Quan sát hình bên dưới. Ở vòng đầu tiên, việc chọn \(1\) hay chọn \(\hat{1}\) là tương đương nhau. Tất cả các hoán vị được tạo ra dưới hai lựa chọn này đều trùng lặp. Do đó, chúng ta nên cắt tỉa \(\hat{1}\).

Tương tự, sau khi chọn \(2\) ở vòng đầu tiên, các phần tử \(1\) và \(\hat{1}\) ở vòng thứ hai cũng tạo ra các nhánh trùng lặp, vì vậy \(\hat{1}\) ở vòng thứ hai cũng nên bị cắt tỉa.

Về mặt bản chất, mục tiêu của chúng ta là đảm bảo rằng nhiều phần tử bằng nhau chỉ được chọn một lần trong một vòng lựa chọn cụ thể.

Cài đặt mã nguồn

Dựa trên mã nguồn từ bài toán trước, chúng ta khởi tạo một tập hợp băm duplicated trong mỗi vòng lựa chọn để ghi lại những phần tử nào đã được thử trong vòng đó, và cắt tỉa các phần tử bằng nhau:

[file]{permutations_ii}-[class]{}-[func]{permutations_ii}

Giả sử các phần tử đôi một khác nhau, có \(n!\) (giai thừa) hoán vị của \(n\) phần tử. Khi ghi lại kết quả, chúng ta cần sao chép một danh sách có độ dài \(n\), tốn thời gian \(O(n)\). Do đó, độ phức tạp thời gian là \(O(n! \cdot n)\).

Độ sâu đệ quy tối đa là \(n\), sử dụng không gian ngăn xếp (stack frame) \(O(n)\). selected sử dụng không gian \(O(n)\). Có tối đa \(n\) tập hợp duplicated tồn tại đồng thời, sử dụng không gian \(O(n^2)\). Do đó, độ phức tạp không gian là \(O(n^2)\).

So sánh hai phương pháp cắt tỉa

Lưu ý rằng mặc dù cả selected và duplicated đều được sử dụng để cắt tỉa, nhưng chúng có mục tiêu khác nhau.

• Cắt tỉa các lựa chọn trùng lặp: Chỉ có một selected duy nhất trong suốt quá trình tìm kiếm. Nó ghi lại những phần tử nào nằm trong trạng thái hiện tại, và mục đích của nó là ngăn một phần tử xuất hiện lặp lại trong state.
• Cắt tỉa các phần tử bằng nhau: Mỗi vòng lựa chọn (mỗi lời gọi hàm backtrack) chứa một tập hợp duplicated. Nó ghi lại những phần tử nào đã được chọn trong vòng lặp hiện tại (vòng lặp for), và mục đích của nó là đảm bảo rằng các phần tử bằng nhau chỉ được chọn một lần.

Hình dưới đây thể hiện phạm vi ảnh hưởng của hai điều kiện cắt tỉa. Lưu ý rằng mỗi nút trong cây đại diện cho một lựa chọn, và các nút trên đường đi từ gốc đến nút lá tạo thành một hoán vị.