Dùng giải thuật để xáo trộn các dãy số không trùng lặp?

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ử:
CODE
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ơ", có thể là như sau:

CODE
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 := p[i+1] end loop; p[k] := h
LietKeHoanVi(k-1, p)
end loop
else --- tai day k = 1
print(p) --- in ra hoan vi p[1...N]
end if
end


Cách dùng (chẳng hạn N = 3):
CODE
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.
.....
Bạn có thể tham khảo trang web này để làm tiếp được nhé :http://diendantoanhoc.net/forum/lofiversion/index.php?t4440.html