Chúng ta có thể viết thuật toán sinh tổ hợp chập k của n với Pascal như sau:
procedure generateCombinations(n, k: integer);
var
comb: array[1..k] of integer;
i, j: integer;
begin
for i := 1 to k do
comb[i] := i - 1;
repeat
// In ra các phần tử của tổ hợp chập k hiện tại
for i := 1 to k do
write(comb[i], ' ');
writeln;
// Tìm phần tử cuối cùng của tổ hợp chập k hiện tại có thể tăng lên được
j := k;
while (j > 0) and (comb[j] = n - k + j) do
dec(j);
if j > 0 then
begin
// Tăng phần tử này lên 1 đơn vị
inc(comb[j]);
// Cập nhật các phần tử sau phần tử vừa tăng lên để đảm bảo tổ hợp là tăng dần
for i := j + 1 to k do
comb[i] := comb[i - 1] + 1;
end;
until j = 0;
end;
Thuật toán này sử dụng một mảng comb để lưu trữ các phần tử của tổ hợp chập k hiện tại. Ban đầu, mỗi phần tử trong mảng comb sẽ được khởi tạo là một giá trị tùy ý từ 1 đến k. Sau đó, vòng lặp sẽ lặp lại cho đến khi tất cả các tổ hợp chập k của tập n được liệt kê.
Trong mỗi vòng lặp, thuật toán sẽ in ra các phần tử của tổ hợp chập k hiện tại, sau đó tìm phần tử cuối cùng của tổ hợp chập k hiện tại có thể tăng lên được. Nếu tìm được phần tử này, thuật toán sẽ tăng nó lên 1 đơn vị và cập nhật các phần tử sau phần tử đó để đảm bảo rằng tổ hợp là tăng dần. Nếu không tìm được phần tử có thể tăng lên được, tức là đã liệt kê hết tất cả các tổ hợp chập k của tập n, thuật toán sẽ dừng lại.
Với thuật toán này, chúng ta có thể tìm được tất cả các tổ hợp chập k của một tập n bất kỳ, và các tổ hợp này sẽ được liệt kê theo thứ tự tăng dần.
Dưới đây là một ví dụ cụ thể về cách cài đặt thuật toán sinh tổ hợp chập k của n với Pascal:
program CombinationGenerator;
const
MAX_N = 100;
MAX_K = 10;
var
n, k: integer;
procedure generateCombinations(n, k: integer);
var
comb: array[1..MAX_K] of integer;
i, j: integer;
begin
for i := 1 to k do
comb[i] := i - 1;
repeat
// In ra các phần tử của tổ hợp chập k hiện tại
for i := 1 to k do
write(comb[i], ' ');
writeln;
// Tìm phần tử cuối cùng của tổ hợp chập k hiện tại có thể tăng lên được
j := k;
while (j > 0) and (comb[j] = n - k + j) do
dec(j);
if j > 0 then
begin
// Tăng phần tử này lên 1 đơn vị
inc(comb[j]);
// Cập nhật các phần tử sau phần tử vừa tăng lên để đảm bảo tổ hợp là tăng dần
for i := j + 1 to k do
comb[i] := comb[i - 1] + 1;
end;
until j = 0;
end;
begin
// Nhập giá trị của n và k từ bàn phím
write('Nhap n: ');
readln(n);
write('Nhap k: ');
readln(k);
// Kiểm tra tính hợp lệ của n và k
if (n < k) or (n > MAX_N) or (k > MAX_K) then
writeln('Gia tri khong hop le!')
else
begin
// Liệt kê tất cả các tổ hợp chập k của tập n
writeln('Cac to hop chap ', k, ' cua tap {1, 2, ..., ', n, '}:');
generateCombinations(n, k);
end;
end.
Trong ví dụ này, chúng ta sử dụng một hằng số MAX_N để giới hạn giá trị của n, và một hằng số MAX_K để giới hạn giá trị của k và kích thước của mảng comb. Sau đó, chúng ta sử dụng hàm generateCombinations để sinh các tổ hợp chập k của tập n, và in ra các tổ hợp này theo thứ tự tăng dần.
Tập hợp ban đầu có 5 phần tử là {1, 2, 3, 4, 5}. Chúng ta muốn liệt kê tất cả các tổ hợp chập 3 của tập hợp này. Sử dụng chương trình Pascal ở trên, ta có thể in ra kết quả như sau:
Cac to hop chap 3 cua tap {1, 2, 3, 4, 5}:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Chúc bạn thành công!