[Bài toán] Liệt kê tập con của tập n phần tử.

Bài toán: Cho X = {1, 2,3,.., n}. Hãy liệt kê tất cả các tập con k phần tử của X (k<=n).
Giải: Mỗi tập con của tập hợp X có thể biểu diễn bằng bộ có thứ tự gồm k thành phần a = (a1a2..ak) thoả mãn 1 ≤a1 ≤a2 ≤..≤ak ≤n.
Trên tập các tập con k phần tử của X có thể xác định nhiều thứ tự khác nhau. Thứ tự dễ nhìn thấy nhất là thứ tự từ điển được định nghĩa như sau:
Ta nói tập con a = a1a2... ak đi trước tập con a’ = a1’a2’...ak’ trong thứ tự từ điển và ký hiệu là a<a’, nếu tìm được chỉ số j ( 1 ≤j ≤k ) sao cho: a1= a1’, a2 = a2’,..., aj-1= a’j-1, aj< a’j.
Chẳng hạn X = { 1, 2, 3, 4, 5 }, k = 3. Các tập con 3 phần tử của X được liệt kê theo thứ tự từ điển như sau:
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
Như vậy, tập con đầu tiên  trong thứ tự từ điển là (1, 2,.., k) và tập con cuối cùng là (n-k+1,n-k+2,.., n). Giả sử a = (a1, a2,.., ak) là tập con hiện tại và chưa phải là cuối cùng, khi đó có thể chứng minh được rằng tập con kế tiếp trong thứ tự từ điển có thể được xây dựng bằng cách thực hiện các qui tắc biến đổi sau đối với tập con đang có.

1. Tìm từ bên phải dãy a1, a2,.., ak phần tử ai≠n – k + i
2. Thay ai bởi ai+1,
3. Thay aj bởi ai+ j – i, với j:= i+1, i + 2,...,k

Chẳng hạn với n = 6, k =4. Giả sử ta đang có tập con (1, 2, 5, 6), cần xây dựng tập con kế tiếp nó trong thứ tự từ điển. Duyệt từ bên phải ta nhận được i =2, thay a2 bởi a2+ 1 = 2 + 1 =3.
Duyệt j từ i + 1 = 3 cho đến k, ta thay thế a3= a2+ 3 – 2 = 3 + 3 - 2 = 4, a4= a2 + 4 - 2 = 3 + 4 – 2 = 5 ta nhận được tập con kế tiếp là ( 1, 3, 4, 5).
Với qui tắc sinh như trên, chúng ta có thể mô tả bằng thuật toán sau:
Thuật toán liệt kê tập con kế tiếp m phần tử của tập n phần tử:  

#include <stdio.h> 
#include <conio.h> 
#define TRUE 1 
#define FALSE 0 
#define MAX 100 
int n, k, count, C[MAX], Stop;
void Init(void){
 int i;
 printf("\n Nhap n="); scanf("%d", &n);
 printf("\n Nhap k="); scanf("%d", &k);
 for (i = 1; i <= k; i++)
  C[i] = i;
}
void Result(void){
 int i; count++;
 printf("\n Tap con thu %d:", count);
 for (i = 1; i <= k; i++)
  printf("%3d", C[i]);
}
void Next_Combination(void){
 int i, j;
 i = k;
 while (i > 0 && C[i] == n - k + i)
  i--;
 if (i > 0) {
  C[i] = C[i] + 1;
  for (j = i + 1; j <= k; j++)
   C[j] = C[i] + j - i;
 }
 else Stop = TRUE;
}
void Combination(void){
 Stop = FALSE;
 while (!Stop){
  Result(); Next_Combination();
 }
}
void main(void){
 Init();
 Combination();
 getch();
}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.