Bài toán liệt kê
Thứ tự từ điển
Trong các bộ từ điển, các từ được liệt kê theo thứ tự được gọi là
thứ tự từ điển. Cho hai từ dưới dạng xâu của các kí tự
x = x1x2...xm
y = y1y2...yn
Từ x được gọi là đứng trước từ y theo thứ tự từ điển nếu tồn tại
chỉ số i, sao cho
xj + 1 đứng trước yj + 1
Chú ý: Nếu j>m thì ta coi xj là kí tự rỗng, tương tự nếu j>n thì
coi yj là kí tự rỗng, kí tự rỗng đứng trươc mọi kí tự khác.
[sửa] Liệt kê các hoán vị của tập n phần tử
Việc liệt kê toàn bộ các hoán vị của tập X = {x1,x2,...,xm} được
quy về việc liệt kê tất cả n! hoán vị của tập chỉ số {1,2,...,n}. Ta
sẽ liệt kê các hoán vị của n số tự nhiên {1,2,...,n} theo thứ tự từ
điển. Nhận xét rằng, khi xếp theo thứ tự từ điển, hoán vị đứng
trước tiên sẽ là hoán vị (1,2,3,...,n − 1,n), hoán vị đứng cuối
cùng sẽ là hoán vị (n,n − 1,...,2,1). Ví dụ với n=5, hoán vị đứng
đầu là (1,2,3,4,5), đứng cuối là (5,4,3,2,1). Trong hoán vị đầu
tiên mỗi số đều nhỏ hơn số đứng ngay sau nó, trong hoán vị cuối
cùng thì ngược lại. Vậy kế tiếp sau hoán vị đầu tiên là hoán vị
nào?
[sửa] Hoán vị kế tiếp của một hoán vị (theo thứ tự từ điển)
Giả sử có hoán vị
x = (x1,x2,...,xn − 1,xn) của n số 1,2,...,n.
Thuật toán sinh hoán vị kế tiếp
1. Tìm từ bên phải sang chỉ số i sao cho xi − 1 < xi.
2. Nếu không tìm thấy thì trả lời x là hoán vị cuối cùng,
không có hoán vị kế tiếp.
3. Nếu có i như vậy:
sắp xếp các giá trị xi,...,xn theo thứ tự tăng dần.
đổi chỗ xi − 1 cho phần tử lớn hơn xi − 1 gần nhất
trong các giá trị xi,...,xn
Ví dụ: với n=5
kế tiếp của hoán vị (1,2,3,4,5) là hoán vị (1,2,3,5,4)
kế tiếp của hoán vị (1,2,3,5,4) là hoán vị (1,2,4,3,5)
kế tiếp của hoán vị (1,2,4,3,5) là hoán vị (1,2,4,5,3)
...
kế tiếp của hoán vị (5,4,3,1,2) là hoán vị (5,4,3,2,1)
[sửa] Thuật toán liệt kê tất cả các hoán vị của n số 1,2,...,n
1. Khới tạo: x = (1,2,...,n)
2. Tìm x' là hoán vị kế tiếp của x
3. Nếu không tìm được thì dừng.
4. Nếu thấy,thay x bằng x' quay lại 2.
Ví dụ: Liệt kê 24 hoán vị của 1,2,3,4 theo thứ tự từ điển
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321.
=== Liệt kê các tổ hợp chập k của tập n phần tử 1,2,3,4,5,6