sinh các hoán vị và tổ hợp

SI N H CÁC HOÁN V Ị V À T Ổ HỢ P . S inh các h o á n v ị:

Có nhiều thuật toán đã được phát triển để sinh ra n! hoán vị của tập

{1,2,...,n}. 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ị a1a2...an được gọi là đi trước hoán vị b1b2...bn nếu tồn tại k (1 ≤ k ≤ n), a1 = b1, a2 = b2,..., ak-1 = bk-1 và ak

< bk.

Thuật toán sinh các hoán vị của tập {1,2,...,n} dựa trên thủ tục xây dựng

hoán vị kế tiếp, theo thứ tự từ điển, từ hoán vị cho trước a1 a2 ...an. Đầu tiên nếu an-1

< an thì rõ ràng đổi chỗ an-1 và an cho nhau thì sẽ nhận được hoán vị mới đi liền sau

hoán vị đã cho. Nếu tồn tại các số nguyên aj và aj+1 sao cho aj < aj+1 và aj+1 > aj+2 > ...

> an, 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ố đầu nhỏ hơn số sau. Sau đó, để nhận được hoán vị liền sau ta đặt vào vị trí thứ j số nguyên nhỏ nhất trong các số lớn hơn aj của tập aj+1, aj+2, ..., an, rồi liệt kê theo thứ tự tăng dần của các số còn lại của aj, aj+1, aj+2, ..., an vào các vị trí j+1, ..., n. Dễ thấy không có hoán vị nào đi sau hoán vị xuất phát và đi trước hoán vị vừa tạo ra.

Thídụ11:Tìm hoán vị liền sau theo thứ tự từ điển của hoán vị 4736521.

Cặp số nguyên đầu tiên tính từ phải qua trái có số trước nhỏ hơn số sau là a3

= 3 và a4 = 6. Số nhỏ nhất trong các số bên phải của số 3 mà lại lớn hơn 3 là số 5. Đặt số 5 vào vị trí thứ 3. Sau đó đặt các số 3, 6, 1, 2 theo thứ tự tăng dần vào bốn vị trí còn lại. Hoán vị liền sau hoán vị đã cho là 4751236.

procedureHoán vị liền sau (a1, a2, ..., an) (hoán vị của {1,2,...,n} khác (n, n－1, ...,

2, 1))

j := n － 1

whileaj > aj+1

j := j － 1 {j là chỉ số lớn nhất mà aj < aj+1}

k := n

whileaj > ak

k := k - 1 {ak là số nguyên nhỏ nhất trong các số lớn hơn aj và bên

phải aj}

r := n

đổi chỗ (aj, ak)

s := j + 1

whiler > s

đổi chỗ (ar, as)

r := r - 1 ; s := s + 1

{Điều này sẽ xếp phần đuôi của hoán vị ở sau vị trí thứ j theo thứ tự tăng dần.}

S inh 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 1-1 giữa các tập con của {a1,a2,...,an} và xâu nhị phân độ dài n.

Ta thấy một xâu nhị phân độ dài n cũng là khai triển nhị phân của một số

nguyên nằm giữa 0 và 2n － 1. Khi đó 2n 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 nhỏ 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 bằng 0 và đặt số 1 vào chính vị trí này.

procedureXâu nhị phân liền sau (bn-1bn-2...b1b0): xâu nhị phân khác (11...11)

i := 0

whilebi = 1

b egin

e n d

bi := 1

bi := 0

i := i + 1

Tiếp theo chúng ta sẽ trình bày thuật toán tạo các tổ hợp chập k từ n phần tử

{1,2,...,n}. Mỗi tổ hợp chập k có thể biểu diễn bằng một xâu tăng. Khi đó có thể liệ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 a1a2...ak bằng cách sau. Trước hết, tìm phần tử đầu tiên ai trong dãy đã cho kể từ phải qua trái sao cho ai ≠ n － k + i. Sau đó thay ai bằng ai + 1 và aj bằng ai + j － i + 1 với j = i

+ 1, i + 2, ..., k.

Thídụ12: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}.

Ta thấy từ phải qua trái a2 = 2 là số hạng đầu tiên của tổ hợp đã cho thỏa mãn

điều kiện ai ≠ 6 － 4 + i. Để nhận được tổ hợp tiếp sau ta tăng ai lên một đơn vị, tức

a2 = 3, sau đó đặt a3 = 3 + 1 = 4 và a4 = 3 + 2 = 5. Vậy tổ hợp liền sau tổ hợp đã cho là {1,3,4,5}. Thủ tục này được cho dưới dạng thuật toán như sau.

procedureTổ hợp liền sau ({a1, a2, ..., ak}: tập con thực sự của tập {1, 2, ..., n}

không bằng {n － k + 1, ..., n} với a1 < a2 < ... < ak)

i := k

whileai = n － k + i i := i － 1

ai := ai + 1

forj := i + 1 tok

aj := ai + j － i