Liệt kê tập con k phần tử bằng phương pháp sinh

đăng lúc

Bài toán liệt kê tập con k phần tử là bài toán cổ điển trong loạt bài minh họa về Giải thuật lập trình. Để giải quyết bài toán này, ta có thể dùng phương pháp sinh hoặc thuật toán quay lui. Trong bài này, mình sẽ nói về cách liệt kê các tập con k phần tử sử dụng phương pháp Sinh.

Bài toán liệt kê tập con k phần tử là bài toán cổ điển trong loạt bài minh họa về Giải thuật lập trình. Để giải quyết bài toán này, ta có thể dùng phương pháp sinh hoặc thuật toán quay lui. Trong bài này, mình sẽ nói về cách liệt kê các tập con k phần tử sử dụng phương pháp Sinh.

Nếu các bạn muốn tham khảo cách giải bài toán này bằng phương pháp sinh thì có thể đọc bài này : Liệt kê tập quay lui tập con k phần tử.


Yêu cầu : Viết chương trình in ra toàn bộ tập con k phần tử không có tính thứ tự từ một tập chứa n phần tử (tập n : 1, 2, 3, 4, 5 ,..... n).

Input : giá trị của n và k.

Output : tất cả các tập con k phần tử của tập n phần tử.

Ví dụ :

Input : n = 5, k = 3.  (Với n = 5 thì tập mẹ sẽ là 1, 2, 3, 4, 5)

Output :
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ận xét :

- NX1 :  Số tập con k phần tử không có tính thứ tự của một tập n phần tử là nCk. (nCk là kí hiệu khi bấm máy tính casio nhé :P)

Như ví dụ bên trên thì sẽ có 5C3 = 10

- NX2 : ta dễ dàng nhận thấy giá trị của một số tại vị trí i (i ∈ [1, k]) nào đó trong bộ k phần tử kia sẽ có thể có giá trị lớn nhất là : n - k + i.

Ví dụ với tập con 1 2 3 trong ví dụ trên, thì phần tử thứ 1 có giá trị là 1, phần tử thứ 2 có giá trị là 2, phần tử thứ 3 có giá trị là 3.

Ta thấy rằng giá trị của : - phần tử thứ 1 (i = 1) có thể đạt đến : 5 - 3 + 1 = 3. (n - k + i)
                                          - phần tử thứ 2 (i = 2) có thể đạt đến : 5 - 3 + 2 = 4. (n - k + i)
                                          - phần tử thứ 3 (i = 3) có thể đạt đến : 5 - 3 + 3 = 5. (n - k + i)

Hãy nhìn vào bộ số cuối cùng trong Output của ví dụ bên trên. Khi đã in ra bộ số 3 4 5 tức là giá trị tại các vị trí đều đã đặt đến max nghĩa là đã tìm thấy tập con cuối cùng. Còn ngược lại thì nghĩa là vẫn chưa tìm ra tập con cuối cùng. (Tập con k phần tử không xét tính thứ tự.)

Ví dụ tập 1 4  5 chưa phải tập con cuối cần in ra dù giá trị của phần tử 2 và 3 đã đạt đến giá trị lớn nhất có thể đạt đươc tại vị trí của chúng.

- NX3 :  nhìn vào các bộ số liệt kê trong ví dụ, ta thấy giá trị của các vị trí sau luôn lớn hơn giá trị của giá trị trước. Gía trị nhỏ nhất của phần tử tại vị trí i có thể đạt được là giá trị của vị trí (i - 1) cộng với 1.

Trước khi đọc nhận xét, ý tưởng bến dưới : các bạn hãy thử nhìn vào Output ở ví dụ bên trên và NX2, NX3 coi như là 1 gợi ý để nghĩ ra cách giải quyết bài toán này. Vì thứ tự của các chuỗi trong ví dụ trên cũng chính là thứ tự của các dãy nhị phân được in ra khi chạy chương trình.

Dù nghĩ ra hay không, bạn hãy cứ thử đọc ý tưởng để tham khảo nhé.

Ý tưởng :  Từ  NX2 và NX3, ta sẽ tạo 1 mảng k phần tử (1, 2, ....., k). Sau đó ta sẽ duyệt từ vị trí cuối mảng đi lên. Khi đi lên, nếu tại vị trí i nào đó mà giá trị của phần tử tại vị trí i này chưa đạt giá trị max (n - k i) thì sẽ tiến hành tăng giá trị phần tử tại vị trí i này lên 1 đơn vị. Sau đó gán cho toàn bộ phần tử sau phía sau vị trí i giá trị bằng giá trị phần tử liền trước nó cộng thêm 1.

Các bước viết chương trình :

- Yêu nhập vào giá trị n và k.
- Khai báo mảng gồm k phần tử.
- Gán giá trị cho các phần tử mảng trên từ 1 tới k.(tập con đầu tiên) và in ra.
- Tạo 1 vòng lặp duyệt từ cuối mảng (vị trí k - 1) đi lên. khi gặp phần tử i nào đó có giá trị bé hơn n - k + i thì tăng giá trị phần tử này lên 1 đơn vị. Sau đó tạo một vòng lặp con trong vòng lặp ban đầu, gán toàn bị phần tử phía sau i (từ i + 1 đến k -1) bằng giá trị của phần tử liền trước nó cộng 1.
- Gán lại giá trị của i về giá trị cuối mảng để duyệt lại. (Lưu ý : nếu vòng lặp chạy từ k - 1 về 0, thì sẽ gán i = k. Tại sao là i = k chứ không phải i = k - 1 thì các bạn thử nghĩ xem nhé.)
- Cứ thế khi tất cả các phần tử đều đạt giá trị max thì chương trình sẽ tự dừng lại.

C code liệt kê tập con k phần tử :

#include<stdio.h>
#include<conio.h>

int main()
{
    // nhap n va k
    int n;
    printf("Nhap vao n : ");
    scanf("%d", &n);

    int k;
    printf("\nNhap vao k: ");
    scanf("%d", &k);

    // khoi tao mang k phan tu
    int mang[k];

    printf("\nTap con liet ke duoc :\n");

    // in ra tap con dau tien
    int i;
    for(i = 0; i < k; i++)
    {
        mang[i] = i + 1;    // khoi tao mang[i] = i + 1;
        printf("%d  ", mang[i]);
    }
    printf("\n");

    // xu ly
    for(i = k - 1; i >= 0; i--)
    {
        if(mang[i] < n - k + i + 1)  // neu phan tu vi tri i nho hon gia tri max tai vi tri nay
        {
            mang[i]++;  // tang len 1 don vi

            int j;
            for(j =  i + 1; j < k; j++)
            {
                mang[j] = mang[j-1] + 1;   // gan lai gia tri cho cac phan tu phia sau
            }

            // in ra bo so moi tao duoc
            for(j = 0; j < k; j++)
            {
                printf("%d  ", mang[j]);
            }
            printf("\n");

            i = k;  // gan i = k de khi het vong lap i-- nen i se = k - 1, tu do chay lai tu vi tri cuoi.
                    // gan i = k - 1 la sai vi khi het vong lap hien tai i-- se thanh k - 2.
        }
    }

    getch();
    return 0;
}

Nếu có thắc mắc gì thì các bạn hãy comment ở bên dưới bài viết này.

Tham khảo tại : Giải thuật và lập trình - Lê Minh Hoàng.

Nội dung chính
    Bài đăng mới hơn Bài đăng cũ hơn