Đầu tiên, chúng ta sẽ thảo luận và triển khai cả thuật toán đệ quy và thuật toán lặp để tạo ra tất cả các kết hợp có kích thước nhất định. Sau đó, chúng tôi sẽ xem xét các giải pháp sử dụng các thư viện Java phổ biến
2. Tổng quan về kết hợp
Nói một cách đơn giản, một sự kết hợp là một tập hợp con của các phần tử từ một tập hợp nhất định
Không giống như hoán vị, thứ tự chúng ta chọn các phần tử riêng lẻ không quan trọng. Thay vào đó, chúng ta chỉ quan tâm liệu một phần tử cụ thể có nằm trong vùng chọn hay không
Ví dụ, trong một trò chơi bài, chúng ta phải chia 5 quân bài trong bộ gồm 52 quân bài. Chúng tôi không quan tâm đến thứ tự chọn 5 thẻ. Thay vào đó, chúng tôi chỉ quan tâm những lá bài nào có trong tay
Một số vấn đề yêu cầu chúng tôi đánh giá tất cả các kết hợp có thể. Để làm điều này, chúng tôi liệt kê các kết hợp khác nhau
Số cách khác nhau để chọn phần tử “r” từ tập hợp phần tử “n” có thể được biểu diễn bằng toán học theo công thức sau
Do đó, số cách chọn phần tử có thể tăng theo cấp số nhân trong trường hợp xấu nhất. Do đó, đối với các quần thể lớn, có thể không liệt kê được các lựa chọn khác nhau
Trong những trường hợp như vậy, chúng tôi có thể chọn ngẫu nhiên một vài lựa chọn đại diện. Quá trình này được gọi là lấy mẫu
Tiếp theo, chúng tôi sẽ xem xét các thuật toán khác nhau để liệt kê các kết hợp
3. Thuật toán đệ quy để tạo kết hợp
Các thuật toán đệ quy thường hoạt động bằng cách phân vùng một vấn đề thành các vấn đề nhỏ hơn tương tự. Quá trình này tiếp tục cho đến khi chúng ta đạt đến điều kiện kết thúc, đây cũng là trường hợp cơ sở. Sau đó, chúng tôi giải quyết trường hợp cơ sở trực tiếp
Chúng ta sẽ thảo luận về hai cách để chia nhỏ nhiệm vụ chọn các phần tử từ một tập hợp. Cách tiếp cận đầu tiên phân chia vấn đề theo các phần tử trong tập hợp. Cách tiếp cận thứ hai phân chia vấn đề bằng cách chỉ theo dõi các phần tử đã chọn
3. 1. Phân vùng theo các phần tử trong toàn bộ tập hợp
Hãy phân chia nhiệm vụ chọn “r” phần tử từ “n” mục bằng cách kiểm tra từng mục một. Đối với mỗi mục trong bộ, chúng tôi có thể đưa nó vào lựa chọn hoặc loại trừ nó
Nếu chúng tôi bao gồm mục đầu tiên, thì chúng tôi cần chọn phần tử “r – 1″ từ “n – 1″ mục còn lại. Mặt khác, nếu chúng ta loại bỏ mục đầu tiên, thì chúng ta cần chọn phần tử “r” trong số “n – 1” phần tử còn lại
Điều này có thể được biểu thị bằng toán học như
Bây giờ, hãy xem xét việc triển khai đệ quy của phương pháp này
private void helper[List combinations, int data[], int start, int end, int index] {
if [index == data.length] {
int[] combination = data.clone[];
combinations.add[combination];
} else if [start