PDA

View Full Version : Hướng dẫn Liệt kê hoán vị bằng thuật toán Johnson-Steinhaus-Trotter



Ada
14-05-2011, 01:44 PM
Mã nguồn mình đã gửi tại congdongcviet, ai cần có thể tự tìm. Dưới đây là cơ sở lí thuyết.

================================================== ===
Bài của queensland gửi tại diendantoanhoc.net.
================================================== ===
Chào các bạn, tuần vừa rồi queensland phải giải một bài toán bằng máy tính, tìm được một thuật toán thấy cũng hay hay nên post lên đây cho các bạn xem chơi. Đó là thuật toán Johnson-Steinhaus-Trotter, dùng để liệt kê các hoán vị.

Liệt kê là một vấn đề rất cơ bản của lập trình. Liệt kê có nghĩa là lần lượt duyệt qua từng phần tử của một tập hợp cho trước sao cho mỗi phần tử được duyệt qua đúng một lần, và in ra giá trị của từng phần tử. Tất nhiên hành động "in ra" có thể thay bằng một hành động nào đó khác trên phần tử, vì thế mỗi thuật toán liệt kê cho một tập hợp sẽ là một cái "khung" cơ bản cho nhiều thuật toán xử lý tập hợp ấy. Thí dụ sau đây liệt kê các số chẵn từ 0 đến 2*N:


for i := 0...N loop
print(2*i)
end loop

(Trong bài này không dùng ngôn ngữ lập trình nào cả. Mọi code đều là pseudo-code.)

Vì tập hợp các số chẵn rất đơn giản, thuật toán liệt kê trong trường hợp này chỉ là một vòng lặp.

Bây giờ ta nói đến bài toán chính, là liệt kê các hoán vị. Một hoán vị N phần tử được cho bằng một bảng p[1,...,N], mỗi ô là một số tự nhiên từ 1 đến N, không số nào giống số nào cả. Ví dụ, sau đây là danh sách tất cả các hoán vị 3 phần tử:


1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Làm thế nào để liệt kê tất cả N! hoán vị N phần tử? Thứ tự các hoán vị trong danh sách là không đáng quan tâm, cốt sao liệt kê được càng nhanh càng tốt, bởi vì với N = 16 chẳng hạn, một máy vi tính mạnh cũng phải làm mất vài ngày.

Một thuật toán tự nhiên, có thể nói là "ngây thơ", như sau:


recursive procedure LietKeHoanVi (k, p[])
--- thu tuc nay liet ke moi hoan vi p[1...k]
begin
if k >= 2 then
for c := 1...k loop
h := p[1];
for i := 1...k - 1 loop
p[i] := p[i+1]
end loop;
p[k] := h
LietKeHoanVi(k-1, p)
end loop
else --- k = 1
print(p) --- in ra hoan vi p[1...N]
end if
end

Cách dùng (chẳng hạn N = 3):


p[] = (1, 2, 3)
LietKeHoanVi (3, p)

Diễn tả bằng lời: muốn liệt kê hoán vị các số trong mảng p[1...k], k>=2, ta đặt một số vào vị trí "cố định" ở cuối mảng (p[k]) nhờ hoán vị vòng quanh p[1...k] và liệt kê hoán vị phần còn lại (p[1...k-1]).

Trong thuật toán tự nhiên này, các hoán vị vòng quanh độ dài 2, 3,..., N được sử dụng. Hoán vị vòng quanh độ dài N được dùng N lần, độ dài N-1 dùng (N-1)*N lần, độ dài N-2 dùng (N-2)*(N-1)*N lần, v.v. Bởi vì thời gian thực hiện một hoán vị vòng quanh độ dài N tỷ lệ thuận với N, thuật toán này không hiệu quả lắm.

Thuật toán Johnson-Steinhaus-Trotter sắp trình bày sau đây là một thuật toán liệt kê hoán vị hiệu quả. Từ một hoán vị sinh một hoán vị mới chỉ cần hoán vị đúng một cặp số, và hơn nữa, đó luôn là 2 số đứng liền kế nhau trong mảng.

Thuật toán Johnson-Steinhaus-Trotter dựa trên một ý tưởng đơn giản. Hãy xem liệt kê các hoán vị 2 số:


1 2
2 1

Để liệt kê các hoán vị 3 số, đầu tiên ta chép lại danh sách trên, mỗi hàng được chép lặp 3 lần:


1 2
1 2
1 2

2 1
2 1
2 1

viết thêm số 3 vào cuối hoán vị nhứ nhất, rồi tuần tự "di chuyển" số 3 ra phía đầu hoán vị, ta được 3 hoán vị 3 phần tử:


1 2 3
1 3 2
3 1 2

giữ số 3 ở vị trí đầu một lần nữa, rồi tuần tự "di chuyển" số 3 về phía cuối hoán vị, ta thu được nốt 3 hoán vị 3 phần tử:


3 2 1
2 3 1
2 1 3

Tiếp tục tương tự với số 4, ta sẽ thu được 24 hoán vị 4 phần tử:


1 2 3 4
1 2 4 3
1 4 2 3
4 1 2 3

4 1 3 2
1 4 3 2
1 3 4 2
1 3 2 4

3 1 2 4
3 1 4 2
3 4 1 2
4 3 1 2

4 3 2 1
3 4 2 1
3 2 4 1
3 2 1 4

2 3 1 4
2 3 4 1
2 4 3 1
4 2 3 1

4 2 1 3
2 4 1 3
2 1 4 3
2 1 3 4

Và cứ thế tiếp tục với số 5, 6,..., N. Thuật toán Johnson-Steinhaus-Trotter trình bày theo lối này hẳn là đủ rõ ràng đến mức không cần phải chứng minh rằng nó thực sự liệt kê mọi hoán vị N số, và hơn nữa theo thứ tự sao cho hoán vị thứ i với thứ i+1 chỉ sai khác nhau ở đúng một cặp số đứng liền kế nhau. Thêm vào đó, hoán vị cuối cùng (thứ N!) so với hoán vị đầu tiên (thứ 1) cũng chỉ sai khác nhau ở đúng một cặp số đứng liền kế nhau (cặp nào? câu hỏi này xin nhường cho bạn đọc).


Số 3 (và 4) trong các liệt kê nói trên gọi là số nguyên lưu động. Khi thực hiện trên máy tính ta không liệt kê hết các hoán vị 2 (và 3) ra trước khi liệt kê các hoán vị 3 (và 4), nghĩa là ta phải làm việc đồng thời với nhiều số nguyên lưu động. Để nhớ vị trí của số nguyên lưu động, ta dùng mảng pi[] là hoán vị ngược của p[] theo nghĩa pi[p[x]] = x (với mọi x) và p[pi[k]] = k (với mọi k). Ta còn dùng mảng d[] để ghi nhớ chiều di chuyển của số nguyên lưu động, nghĩa là d[k] = +1 hoặc -1 (với mọi k).


Thuật toán


recursive procedure JohnsonSteinhausTrotter (k, p[], pi[], d[])
--- k = so nguyen luu dong tuc thoi
begin
if k<=N then
JohnsonSteinhausTrotter (k+1, p, pi, d)
for c := 1...k-1 loop
--- doi tri p[x], p[y], trong do x = pi[k], y=x+1 hoac x-1
x := pi[k]; y := x + d[k];
j := p[y];
p[x] := j; pi[j] := x;
p[y] := k; pi[k] := y;
JohnsonSteinhausTrotter (k+1, p, pi, d)
end loop
d[k] := -d[k]
else --- tai day k > N
print(p) --- in ra hoan vi p[1...N]
end if
end


Cách dùng (thí dụ với N=3):


p[1...3] := (1,2,3)
pi[1...3] := (1,2,3)
d[1...3] := (-1,-1,-1)
JohnsonSteinhausTrotter (1, p, pi, d)


Lịch sử và tư liệu

Thuật toán này mang tên Johnson, Steinhaus và Trotter, ba tác giả độc lập với nhau, đã tìm ra và công bố thuật toán trong khoảng thời gian 1959-1963. (Tôi chỉ biết thế thôi, chứ chưa được đọc nguyên tác.) Tuy nhiên, có lẽ họ không phải là những người đầu tiên biết thuật toán này. Sách cổ của nhà thờ Anh quốc từ thế kỷ 16 còn ghi bài toán đánh chuông nhà thờ: bộ chuông có N chiếc chuông kích thước và âm thanh khác nhau; mỗi hồi chuông đánh cả N chiếc mỗi chiếc một lần; cần xây dựng trình tự đánh chuông sao cho tiếng chuông nghe êm tai, nghĩa là không có hồi chuông nào nào giống hồi nào và tiếng chuông ở hai hồi liên tiếp nhau sai khác nhau ít nhất. Sách cổ không ghi lời giải tổng quát nhưng có ghi vài trình tự đánh chuông giống với liệt kê hoán vị Johnson-Steinhaus-Trotter cho N <=6.

Pseudo-code cho procedure JohnsonSteinhausTrotter dịch từ mã nguồn (ngôn ngữ C) của Frank Ruskey, thay đổi một chút không đáng kể. Có thể tiếp cận mã nguồn nguyên bản qua địa chỉ http://www.nist.gov/dads/HTML/johnsonTrotter.html.

================================================== ===
Bài của queensland gửi tại diendantoanhoc.net.
================================================== ===

Đây là một hình minh họa cho tính chất của thuật toán rất đẹp và sinh động: http://members.multimania.nl/permutation/

Ada
15-05-2011, 12:13 PM
Thật ra, trong liệt kê hoán vị (permutation enumeration) thì thuật toán J-S-T không phải là thuật toán nhanh nhất. Trong thư viện chuẩn STL của C++ có một thuật toán hỗ trợ liệt kê hoán vị theo thứ tự từ điển (lexicographic order) nhanh hơn J-S-T, tên là thuật toán L. Cơ sở lí thuyết của L có thể tìm thấy trong quyển sách giáo khoa lập trình danh tiếng của Knuth D.: The Art of Computer Programming.

peterdrew
15-05-2011, 12:24 PM
Thanks bài viết của Ada, đúng là trong làng C Việt có cậu rất thiên về algorithm, Peter rất thích các bài viết của cậu.

Ada
17-05-2011, 05:20 AM
Cám ơn peterdrew. Thật ra bài trên không phải do mình viết, mình chỉ là người sưu tầm. Nhưng lời khen của bạn cũng làm mình rất phấn khởi và muốn đóng góp nhiều hơn nữa.

blackmoonT92
19-05-2011, 07:35 AM
thanks bác nhìu nhé.(Y:DY)(Y:DY)(Y:DY)

doicanhden
27-07-2012, 10:08 PM
Thật ra, trong liệt kê hoán vị (permutation enumeration) thì thuật toán J-S-T không phải là thuật toán nhanh nhất. Trong thư viện chuẩn STL của C++ có một thuật toán hỗ trợ liệt kê hoán vị theo thứ tự từ điển (lexicographic order) nhanh hơn J-S-T, tên là thuật toán L. Cơ sở lí thuyết của L có thể tìm thấy trong quyển sách giáo khoa lập trình danh tiếng của Knuth D.: The Art of Computer Programming.
Không biết Ada có file pdf của cuốn "The Art of Computer Programming" không? Nếu có thì cho tôi 1 cái link nhé. Cám ơn.

luc13aka47
27-07-2012, 10:12 PM
Không biết Ada có file pdf của cuốn "The Art of Computer Programming" không? Nếu có thì cho tôi 1 cái link nhé. Cám ơn.

Google keyword : The Art of Computer Programming site:4shared.com

Thử xem :D

doicanhden
27-07-2012, 10:49 PM
Google keyword : The Art of Computer Programming site:4shared.com

Thử xem :D
Oh, tks, Tôi dùng keyword "The Art of Computer Programming" filetype:pdf nên tìm mãi không ra. Chắc do dung lượng lớn và có nhiều phần.