Sinh các hoán vị và tổ hợp
1. Sinh các hoán vị:
Mọi tập n phần tử đề có thể tương ứng với tập {1, 2,..., n}
Chúng ta có thể liệt kê các hoán vị của một tập bất kỳ gồm n phần tử bằng cách sinh ra các hoán vị của tập n số nguyên dương nhỏ nhất, sau đó thay thế các số nguyên này bằng các phần tử tương ứng của chúng. Có nhiều thuật toán đã được phát triển để sinh ra n! hoán vị của tập này. Chúng ta sẽ mô tả một trong các phương pháp đó, phương pháp liệt kê các hoán vị của tập {1, 2...n} theo thứ tự từ điển.
Khi đó hoán vị a₁, a₂, ..., a_n được gọi là đi trước (nhỏ hơn) hoán vị b₁, b₂, ..., b_n nếu với k nào đó ( 1 ≤ k ≤ n ) , a₁ = b₁ , a₂ = b₂ ,... a_k-1 = b_k-1 và a_k < b_k . Nói cách khác, một hoán vị của tập n số nguyên dương đầu tiên được gọi là đi trước (theo thứ tự từ điển) một hoán vị khác nếu con số của hoán vị đầu tại vị trí đầu tiên mà 2 hoán vị khác nhau, nhỏ hơn con số thuộc hoán vị thứ 2 cũng ở vị trí đó.
Ví dụ 1:
Hoán vị 23415 của tập {1, 2, 3, 4, 5} là đi trước hoán vị 23514, vì những hoán vị này trùng nhau ở 2 vị trí đầu tiên, nhưng số 4 ở vị trí thứ 3 của hoán vị đầu nhỏ hơn số 5 cũng ở vị trí 3 của hoán vị sau. Tương tự hoán vị 41532 là đi trước 52143.

Thuật toán sinh các hoán vị của tập {1, 2, 3... n} dựa trên thủ tục xây dựng hoán vị kế tiếp theo thứ tự từ điển , của hoán vị cho trước a₁, a₂, ..., a_n. Bây giờ chúng ta sẽ chỉ rõ cách xây dựng hoán vị liên tiếp này.

Đầu tiên ta giả sử a_n-1 < a_n. Rõ ràng nếu đổi chỗ a_n-1 và a_n cho nhau thì ta nhận được hoán vị mới (đi sau) hay lớn hơn hoán vị đã cho, và không thể có hoán vị nào khác lớn hơn hoán vị xuất phát mà lại bé hơn hoán vị nhận được bằng việc đổi chỗ a_n-1 và a_n cho nhau. Ví dụ, hoán vị liền tiếp sau hoán vị 234156 là hoán vị 234165. Nếu a_n-1 > a_n thì không thể nhận được hoán vị lớn hơn bằng cách đổi chỗ 2 phần tử này trong hoán vị.

Bây giờ ta xem xét 3 số. Nếu a_n-2 < a_n-1 thì có thể sắp xếp lại 3 số cuối cùng để có thể nhận được một hoán vị mới liền sau hoán vị xuất phát. Đặt số nhỏ hơn trong 2 số a_n-1 và a_n vào vị trí n-2 sau đó đặt số nguyên còn lại và số a_n-2 vào 2 vị trí cuối cùng theo thứ tự tăng dần. Ví dụ hoán vị liền sau hoán vị 234165 là 234516.

Nếu a_n-2 > a_n-1 (và trước đó đã a_n-1 > a_n) khi đó không thể nhận được hoán vị lớn hơn bằng cách đổi chỗ 3 số hạng cuối cùng của hoán vị. Dựa trên những nhận xét này ta có thể mô tả phương pháp tổng quát tạo hoán vị liền sau (theo thứ tự từ điển) của hoán vị cho trước a₁, a₂, ..., a_n như sau:

Trước tiên tìm các số nguyên a_j và a_j+1 sao cho a_j < a_j+1và a_j+1> a_j+2>...>a_n tức là tìm cặp số nguyên liền kề đầu tiên tính từ bên phải sang bên trái của hoán vị mà số trước nhỏ hơn số sau. Sau đó , để nhận được hoán vị liền sau, Khách viếng thăm đặt vào vị trí thứ j số nguyên dương nhỏ nhất trong các số lớn hơn a_j của tập a_j+1, a_j+2..., a_n vào các vị trí j + 1, ..., n. Dễ thấy không có hoán vị nào lớn hơn hoán vị xuất phát và nhỏ hơn hoán vị vừa tạo ra.

Ví dụ 2.

Tìm hoán vị liền sau theo thứ tự từ điển của hoán vị 362541:

Để sinh ra n! hoán vị các số 1, 2, ..., n chúng ta sẽ bắt đầu bằng hoán vị nhỏ nhất theo thứ tự từ điển , tức là 12,...n và áp dụng liên tiếp (n! -1) lần thủ tục đã mô tả ở trên. Bằng cách đó Khách viếng thăm nhận được tất cả các hoán vị của n số nguyên.

Ví dụ 3.

Hãy tạo ra các hoán vị của các số nguyên 1, 2, 3 theo thứ tự từ điển:

Thuật toán sau đây biểu thị thủ tục tìm hoán vị liền sau, theo thứ tự từ điển , một hoán vị cho trước khác hoán vị lớn nhất n, n-1,..., 2, 1.

Thuật toán sinh hoán vị liền sau, theo thứ tự từ điển, từ một hoán vị cho trước:

Sinh các tổ hợp
Làm thế nào để tạo ra tất cả các tổ hợp các phần tử của một tập hữu hạn ? Vì tổ hợp chính là một tập con , nên ta có thể dùng phép tương ứng một - một giữa các tập con của {a₁, a₂, ..., a_n} và xâu nhị phân độ dài n.

Nhớ lại là 1 xâu nhị phân ứng với 1 tập con , tại vị trí k, sẽ có số 1 hoặc số 0 tùy theo phần tử a_k thuộc vòa tập con đó hay không. Nếu có thể liệt kê tất cả các xâu nhị phân ra được thì ta sẽ nhận được tất cả các tập con.

Mặt khác ta thấy một xâu nhị phân độ dài n cũng là triển khai nhị phân của một số nguyên nằm giữa 0 và 2ⁿ - 1 . Khi đó 2ⁿxâu nhị phân có thể liệt kê theo thứ tự tăng dần của số nguyên trong biểu diễn nhị phân của chúng. Chúng ta sẽ bắt đầu từ xâu nhị phân bé nhất 00..00 (n số 0) . Mỗi bước để tìm xâu liền sau ta tìm vị trí đầu tiên tính từ phải qua trái mà ở đó là số 0. Sau đó thay tất cả số 1 ở bên phải số này = 0 và đặt số 1 vào chính vị trí này.

Hãy tìm xâu nhị phân liền sau của 10001 00111:

Thuật toán sinh xâu nhị phân liền sau:

Tiếp theo ta sẽ trình bày thuật toán tạo các tổ hợp chập r từ n phần tử {1, 2...n}. Mỗi tổ hợp chập r có thể biểu diễn bằng một xâu tăng. Khi đó có thể kiệt kê các tổ hợp theo thứ tự từ điển. Có thể xây dựng tổ hợp liền sau tổ hợp a₁, a₂, ..., a_n bằng cách sau. Trước hết, tìm phần tử đầu tiên a_i trong dãy đã cho kể từ phải qua trái sao cho với j = i + 1 , i + 2,..., r. Nào Khách viếng thăm hãy tự chứng minh thủ tục trên sinh ra tổ hợp liền sau. Còn bây giờ ta xét ví dụ minh họa thủ tục này nhé.

Tìm tổ hợp chập 4 từ tập (1, 2, 3, 4, 5, 6) đi liền sau tổ hợp (1, 2, 5, 6):

Thuật toán

Sinh tổ hợp chập R liền sau theo thứ tự từ điển:

Admin đã viết:Ví dụ 3.

Hãy tạo ra các hoán vị của các số nguyên 1, 2, 3 theo thứ tự từ điển:

Thuật toán sau đây biểu thị thủ tục tìm hoán vị liền sau, theo thứ tự từ điển , một hoán vị cho trước khác hoán vị lớn nhất n, n-1,..., 2, 1.

Thuật toán sinh hoán vị liền sau, theo thứ tự từ điển, từ một hoán vị cho trước:

đ/c Admin cần chú ý những câu lệnh trong và ngoài vòng lặp nhé. Những chỗ tôi đánh dấu đỏ ý.