Sự quan trọng của thuật toán Sinh
trong lập trình , thuật toán Sinh có vai trò quan trọng trong việc giải quyết nhiều bài toán khác nhau. Bài viết này sẽ giới thiệu về ba thuật toán cơ bản: Sinh nhị phân, Sinh tổ hợp và Sinh hoán vị.
Sinh nhị phân
Thuật toán Sinh nhị phân là thuật toán đầu tiên mình muốn đề cập vì nó rất đơn giản. Với một số N cho trước, ta cần liệt kê tất cả các cấu hình gồm K chữ số 0 hoặc 1. Tuy nhiên, không chỉ cần dùng phép chia lấy dư để sinh ra chuỗi nhị phân như khi chuyển đổi từ hệ thập phân sang nhị phân. Chúng ta cần tìm ra một quy luật đơn giản hơn để sinh ra các chuỗi này.
Thuật toán Sinh nhị phân: Cho một mảng gồm n kí tự 0. Bắt đầu duyệt từ phải sang trái, nếu gặp số 1, đổi thành 0 và tiếp tục duyệt sang trái. Nếu gặp số 0, đổi thành 1 và kết thúc thuật toán. Khi mảng chỉ chứa số 1, thuật toán kết thúc.
void binaryGen(int B[], int n) { i = n; while (i > 0 && B[i] == 1) { B[i] = 0; i--; } if (i == 0) return; else B[i] = 1; }Sinh tổ hợp
Tiếp theo là thuật toán Sinh tổ hợp. Thuật toán này giúp liệt kê tất cả các tổ hợp chập K của N phần tử. Khi liệt kê, chúng ta ưu tiên hiển thị các phần tử theo thứ tự từ điển. Ví dụ: Với bài toán liệt kê tất cả các phần tử gồm 4 phần tử trong tổ hợp 6 phần tử, ta có các tổ hợp sau:
1 2 3 4 1 2 3 5 ... 3 4 5 6
Quy tắc là nếu vị trí j bằng N - K + j, giá trị tại vị trí j phải là giá trị của tổ hợp cuối cùng. Ví dụ, ở vị trí thứ 4, giá trị tại vị trí đó phải là 6 - 4 + 4 = 6. Từ đó, ta có thể áp dụng thuật toán để liệt kê các tổ hợp.
Thuật toán Sinh tổ hợp: Cho một mảng gồm N phần tử và một giá trị K cho trước. Bắt đầu duyệt từ phải sang trái, nếu giá trị tại vị trí j khác với N - K + j, dừng lặp và giá trị aj = aj + 1. Từ vị trí j + 1 đến N, các giá trị sẽ được tính từ giá trị aj đã được cập nhật, tăng dần theo thứ tự từ điển.
void combinationGen(int B[], int K) { i = K; while (B[i] == N - K + i) i--; B[i]++; for (j = i + 1; j = N; j++) B[j] = B[i] + j - i; }Sinh hoán vị
Cuối cùng là thuật toán Sinh hoán vị. Tuy có vẻ giống thuật toán Sinh tổ hợp, nhưng thuật toán này khác hoàn toàn. Với N phần tử đã được sắp xếp theo thứ tự từ điển, ta cần liệt kê tất cả các cấu hình được tạo bởi N phần tử đó. Ví dụ, với bài toán liệt kê tất cả các hoán vị của một mảng gồm 6 phần tử từ 1 đến 6, ta có các hoán vị sau:
1 2 3 4 5 6 1 2 3 4 6 5 ... 6 5 4 3 2 1
Quy tắc là duyệt từ trái sang phải, nếu gặp phần tử nào tại vị trí j mà nhỏ hơn phần tử tại vị trí j + 1, dừng lặp. Sau đó, tìm giá trị tại vị trí k từ vị trí j + 1 đến N sao cho giá trị đó nhỏ nhất. Hoán đổi hai giá trị tại vị trí k và j, sau đó đảo ngược các giá trị từ vị trí j + 1 đến N.
Thuật toán Sinh hoán vị: Với một mảng gồm N phần tử đã được sắp xếp theo thứ tự từ điển tăng dần. Bắt đầu duyệt từ trái sang phải, nếu gặp phần tử nào tại vị trí j nhỏ hơn phần tử tại vị trí j + 1, dừng lặp. Tìm giá trị tại vị trí k từ vị trí j + 1 đến N sao cho giá trị đó nhỏ nhất. Hoán đổi hai giá trị tại vị trí k và j, sau đó đảo ngược các giá trị từ vị trí j + 1 đến N.
void permutationGen(int B[]) { j = N; while (B[j] > B[j + 1]) j--; k = N; while (B[j] > B[k]) k--; t = B[j]; B[j] = B[k]; B[K] = t; r = j + 1; s = N; while(r s){ t = r; r = s; s = t; } }Kết luận
Mặc dù đây là những bài toán cơ bản, nhưng tính ứng dụng của thuật toán Sinh rất phổ biến trong lập trình. Từ ba bài toán trên, chúng ta có thể tuỳ biến và sử dụng thuật toán để giải quyết những bài toán phức tạp hơn.