Phương pháp sinh – Python

Giới thiệu

Trong nội dung bài này, chúng ta cùng nhau tìm hiểu một số bài toán cơ bản về phương pháp sinh.

Phương pháp sinh có thể áp dụng để giải bài toán liệt kê tổ hợp.

Hai điều kiện để có thể áp dụng phương pháp sinh:

Xác định được một thứ tự trên tập các cấu hình tổ hợp. Từ đó suy ra cấu hình đầu tiên và cấu hình cuối cùng.

Xây dựng được thuật toán từ một cấu hình trung gian. Từ đó sinh ra cấu hình kế tiếp.

Những bài toán được tìm hiểu trong bài này:

Sinh các dãy nhị phân độ dài n.

Liệt kê các tập con k phần tử của tập {1, 2, …, n} theo thứ tự từ điển.

Liệt kê các hoán vị của {1, 2, …, n} theo thứ tự từ điển.

Thiết kế chương trình

Bước 1.

Chúng ta tạo một PyDev Project trong Eclipse IDE và đặt tên là PythonAlgorithmGenerationMethod.

Chúng ta tiếp tục tạo package main và class Main.py cùng phương thức main() mặc định.

Bước 2.

Chúng ta tạo package algorithm và class GenerationAlgorithm.py.

Chúng ta cũng định nghĩa những phương thức chính để thực hiện các bài toán đặt ra.

Phương thức generateBinarySequences()

Phương thức generateBinarySequences() được đặc tả để sinh một dãy nhị phân độ dài n.

Một dãy nhị phân độ dài n là một dãy x[1…n] trong đó x[i] ∈ {0, 1} (∀i : 1 ≤ i ≤ n).

Ví dụ: Khi n = 3, chúng ta có 8 dãy nhị phân độ dài 3 được liệt kê lần lượt như sau:

{000; 001; 010; 011; 100; 101; 110; 111}

Như vậy dãy đầu tiên sẽ là 00…0 và dãy cuối cùng sẽ là 11…1.

Ý tưởng giải thuật:

Xét từ cuối dãy về đầu (xét từ hàng đơn vị lên), tìm số 0 gặp đầu tiên.

Nếu thấy thì thay số 0 đó bằng số 1 và đặt tất cả các phần tử phía sau vị trí đó bằng 0.

Nếu không thấy thì thì toàn dãy là số 1, đây là cấu hình cuối cùng.

Bước 1 – 2.

Chúng ta định nghĩa một mảng gồm n phần tử.

Chúng ta gán giá trị 0 cho từng phần tử trong mảng.

Bước 3.

Chúng ta thực hiện thuật toán sinh trong vòng lặp while() {}.

Nội dung chính của thuật toán bao gồm các bước từ 3.1 đến 3.4.

Bước 3.1.

Tại từng bước lặp, chúng ta nhận được một dãy nhị phân.

Chúng ta thêm dãy nhị phân này vào danh sách sequences.

Bước 3.2.

Chúng ta duyệt các phần tử từ cuối dãy trở lại.

Bước 3.3.

Chúng ta thực hiện điều chỉnh giá trị của x[i] và những phần tử đứng sau trên dãy.

Bước 3.4.

Thuật toán sinh dừng lại khi đã sinh ra dãy 11…1.

Thử nghiệm

Chúng ta thử nghiệm phương thức generateBinarySequences() trong class Main.py.

Phương thức generateSubSets()

Phương thức generateSubSets() được đặc tả để liệt kê các tập con k phần tử của tập {1, 2, …, n} theo thứ tự từ điển.

Ví dụ: với n = 5, k = 3, chúng ta ta phải liệt kê đủ 10 tập con:

1.{1, 2, 3} 2.{1, 2, 4} 3.{1, 2, 5} 4.{1, 3, 4} 5.{1, 3, 5} 6.{1, 4, 5} 7.{2, 3, 4} 8.{2, 3, 5} 9.{2, 4, 5} 10. {3, 4, 5}

Như vậy tập con đầu tiên là {1, 2, …, k}.

Tập con kết thúc là {n - k + 1, n - k + 2, …, n}.

Ý tưởng giải thuật:

Tìm từ cuối dãy lên đầu cho tới khi gặp một phần tử x[i] chưa đạt giới hạn trên n - k + i.

Nếu tìm thấy: (i) Tăng x[i] đó lên 1; (ii) Gán tất cả các phần tử sau x[i] bằng giới hạn dưới x[i-1] + 1.

Nếu không tìm thấy tức là mọi phần tử đã đạt giới hạn trên, đây là tập con cuối cùng.