Tuyên bố miễn trừ trách nhiệm: Phương pháp được mô tả bên dưới không phổ biến nhưng thường có thể giải quyết vấn đề hoặc giúp bạn tìm ra giải pháp phù hợp.
Nếu bạn cần kiểm tra sự tồn tại của một hoán vị trong một bài toán hoặc tìm số lượng các hoán vị khớp với nhau hoặc điều gì đó tương tự, thì bạn nên cân nhắc sử dụng lập trình tập hợp con động.
Tham số chính sẽ là một mặt nạ bit, sẽ hiển thị phần tử nào đã được đưa vào hoán vị và phần tử nào chưa. Thông số thứ hai cũng thường được yêu cầu cho biết phần tử nào được đưa vào sau cùng.
Thông thường, các hoán vị có thể được nhìn thấy trong ngữ cảnh của các đường dẫn trong biểu đồ. Theo đó, chúng ta hãy xem xét một ví dụ cổ điển - bài toán đường đi Hamilton.
Đường đi Hamilton là đường đi đơn đi qua mỗi đỉnh của đồ thị đúng một lần. Nó có thể được biểu diễn đơn giản dưới dạng một hoán vị độ dài n, trong đó n là số đỉnh. Thứ tự trong hoán vị này sẽ cho biết thứ tự đi qua các đỉnh trong đường dẫn này.
Để kiểm tra sự hiện diện của một đường dẫn Hamilton trong biểu đồ, hãy bắt đầu động lực học dp[mask][last] - có một đường dẫn đơn giản bỏ qua các đỉnh được đánh dấu bằng các đỉnh trong mặt nạ bit mặt nạ và kết thúc ở đỉnh cuối cùng không.
Các giá trị ban đầu sẽ là dp[2i][i] = true, còn lại là false, nghĩa là luôn có một đường đi trống bắt đầu từ bất kỳ đỉnh nào.
Có giá trị true trong dp[mask][last] chúng ta sẽ thực hiện chuyển tiếp về phía trước, theo nghĩa "mở rộng đường dẫn". Đó là, chúng tôi sẽ tìm kiếm số lượng đỉnh được đánh dấu bằng 0 trong mặt nạ (chúng tôi chưa truy cập chúng trên đường đi) và đồng thời sao cho có một cạnh từ đỉnh cuối cùng đến đỉnh này (đường đi phải được mở rộng bởi một cạnh hiện có). Đó là, chúng tôi làm dp[mask | 2k][k] = true nếu dp[mask][last] = true AND mask & 2k = 0 (đỉnh k chưa được thăm) Và có một cạnh cuối cùng -> k.
Cuối cùng, một đường dẫn Hamilton tồn tại nếu có một giá trị thực trong dp cho các tham số của bitmask tất cả một và bất kỳ đỉnh cuối cùng nào.