8.2.1. Bài toán tìm cấu hình tổ hợp
Có rất nhiều bài toán trong Tin học có yêu cầu dạng: tìm các đối tượng x thoả mãn những điều kiện nhất định trong một tập S các đối tượng cho trước. Bài toán tìm cấu hình tổ hợp là bài toán yêu cầu tìm các đối tượng x có dạng là một vector thoả mãn các điều kiện sau:
1. Đối tượng x gồm n phần tử: x = (x1,x2,…xn).
2. Mỗi phần tử xi có thể nhận một trong các giá trị rời rạc a1, a2, … am.
3. x thoả mãn các ràng buộc có thể cho bởi hàm logic G(x).
Tuỳ từng trường hợp mà bài toán có thể yêu cầu: tìm một nghiệm, tìm tất cả nghiệm hoặc đếm số nghiệm.
Trước hết chúng ta nhắc lại một số cấu hình tổ hợp cơ bản.
a) Tổ hợp
Một tổ hợp chập k của n là một tập con k phần tử của tập n phần tử.
Chẳng hạn tập {1,2,3,4} có các tổ hợp chập 2 là: {1,2}, {1,3, {1,4, {2,3}, {2,4}, {3,4}. Vì trong tập hợp các phần tử không phân biệt thứ tự nên tập {1,2} cũng là tập {2,1} và do đó, ta coi chúng chỉ là một tổ hợp.
Bài toán đặt ra cho chúng ta là hãy xác định tất cả các tổ hợp châp k của tập n phần tử. Để đơn giản ta chỉ xét bài toán tìm các tổ hợp của tập các số nguyên từ 1 đến n. Đối với một tập hữu hạn bất kì, bằng cách đánh số thứ tự của các phần tử, ta cũng đưa được về bài toán đối với tập các số nguyên từ 1 đến n.
Nghiệm cần tìm của bài toán tìm các tổ hợp chập k của n phần tử phải thoả mãn các điều kiện sau:
1. Là một vector x =(x1,x2,…xk)
2. xi lấy giá trị trong tập {1,2,…n}
3. Ràng buộc: xi<xi+1 với mọi giá trị i từ 1 đến k-1.
Có ràng buộc 3 là vì tập hợp không phân biệt thứ tự phần tử nên ta sắp xếp các phần tử theo thứ tự tăng dần.
b) Chỉnh hợp lặp
Chỉnh hợp lặp chập k của n là một dãy k thành phần, mỗi thành phần là một phần tử của tập n phần tử, có xét đến thứ tự và không yêu cầu các thành phần khác nhau.
Một ví dụ dễ thấy nhất của chỉnh hợp lặp là các dãy nhị phân. Một dãy nhị phân độ dài m là một chỉnh hợp lặp chập m của tập 2 phần tử {0,1}. Chẳng hạn 101 là một dãy nhị phân độ dài 3. Ngoài ra ta còn có 7 dãy nhị phân độ dài 3 nữa là 000, 001, 010, 011, 100, 110, 111. Vì có xét thứ tự nên dãy 101 và dãy 011 là 2 dãy khác nhau.
Như vậy, bài toán xác định tất cả các chỉnh hợp lặp chập k của tập n phần tử yêu cầu tìm các nghiệm như sau:
1. Là một vector x =(x1,x2,…xk)
2. xi lấy giá trị trong tập {1,2,…n}
3. Không có ràng buộc nào giữa các thành phần.
Chú ý là cũng như bài toán tìm tổ hợp, ta chỉ xét đối với tập n số nguyên từ 1 đến n. Nếu tập hợp cần tìm chỉnh hợp không phải là tập các số nguyên từ 1 đến n thì ta có thể đánh số các phần tử của tập đó để đưa về tập các số nguyên từ 1 đến n
c) Chỉnh hợp không lặp
Khác với chỉnh hợp lặp là các thành phần được phép lặp lại, tức là có thể giống nhau, chỉnh hợp không lặp chập k của tập n phần tử cũng là một dãy k thành phần lấy từ tập n phần tử có xét thứ tự nhưng các thành phần không được phép giống nhau.
Chẳng hạn có n người, một cách chọn ra k người để xếp thành một hàng là một chỉnh hợp không lặp chập k của n.
Một trường hợp đặc biệt của chỉnh hợp không lặp là hoán vị. Hoán vị của một tập n phần tử là một chỉnh hợp không lặp chập n. Nói một cách trực quan thì hoán vị của tập n phần tử là phép thay đổi vị trí của các phần tử (do đó mới gọi là hoán vị).
Nghiệm của bài toán tìm các chỉnh hợp không lặp chập k của tập n số nguyên từ 1 đến n là các vector x thoả mãn các điều kiện:
1. x có k thành phần: x = (x1,x2,…xk)
2. Các giá trị xi lấy trong tập {1,2,..n}
3. Ràng buộc: các giá trị xi đôi một khác nhau, tức là xi¹xj với mọi i¹j.
Đó là một số bài toán tìm cấu hình tổ hợp cơ bản. Chúng ta sẽ xem xét một số bài toán khác để thấy tính phổ biến của lớp các bài toán dạng này.
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
