Liệt kê hoán vị bằng phương pháp Sinh

đăng lúc

Sinh hoán vị n phần tử. Bài toán liệt kê hoán vị của một tập n phần tử là bài toán cổ điển trong các loạt bài về cấu trúc dữ liệu và giải thuật. Bài toán này có thể giải bằng nhiều cách, phương pháp khác nhau, trong bài này mình sẽ nói về cách giải bài toán này bằng phương pháp Sinh.

Sinh hoán vị của n phần tử. Bài toán liệt kê hoán vị của một tập n phần tử là bài toán cổ điển trong các loạt bài về cấu trúc dữ liệu và giải thuật. Bài toán này có thể giải bằng nhiều cách, phương pháp khác nhau, trong bài này mình sẽ nói về cách giải bài toán này bằng phương pháp Sinh.




Yêu cầu : Viết chương trình liệt kê tất cả các hoán vị của 1 tập gồm n phần tử là n số tự nhiên từ 1 đến n. (1, 2, 3, ..., n)

Input : n (số phần tử của tập).

Output : tất cả các hoán vị của tập n phần tử.

Ý tưởng : Ta sẽ liệt kê các hoán vị theo thứ tự từ điển.

Ví dụ : với n = 4 thì ta sẽ liệt kê theo thứ tự sau :

  1. 1234          2. 1243          3. 1324        4. 1342         5. 1423         6. 1432         7. 2134          8. 2143     9. 2314        10. 2341       11. 2413      12. 2431       13. 3124       14. 3142      15. 3214        16. 3241  17. 3412        18. 3421       19. 4123      20. 4132       21. 4213       22. 4231      23. 4312        24. 4321

Như vậy hoán vị đầu tiên được liệt kê ra là : 1234, còn hoán vị cuối cùng được liệt kê ra là : 4321.

Giờ các bạn hãy nhìn vào các bộ hoán vị trong ví dụ trên theo thứ tự chúng được liệt kê ra. Các bạn sẽ thấy bộ hoán vị được liệt kê phía sau luôn lớn hơn bộ hoán vị phía trước nó. Và đặc biệt hơn là hoán vị phía sau luôn "vừa đủ lớn" hơn hoán vị ngay trước nó.

Vừa đủ lớn là sao ? Ví dụ : với hai hoán vị  1. 1234     và     2. 1243 , thì hoán vị 2 được coi là vừa đủ lớn hơn hoán vị 1 vì dễ thấy 1243 > 1234 và không thể tìm được 1 hoán vị nào trong số 22 hoán vị còn lại (có tất cả 24 hoán vị trong ví dụ trên) có thể chen vào giữ 2 hoán vị này mà vẫn thỏa mãn tính hoán vị sau lớn hơn hoán vị trước. (ví dụ chèn 1324 vào giữ 1234 và 1243 thì sẽ không thỏa mãn vì 1324 > 1243)

Với cặp hoán vị bất kì đứng cạnh nhau nào cũng vậy.

Vậy câu hỏi đặt ra là khi liệt kê làm thế nào để tìm được bộ hoán vị vừa đủ lớn đối với bộ hoán vị vừa được liệt kê ra ngay trước đó ?

Để dễ hiểu, chúng ta sẽ xét ví dụ như sau : giả sử ta đang có một bộ hoán vị như sau : (3, 2, 6, 5, 4, 1). Yêu cầu là tìm bộ hoán vị thỏa mãn tính vừa đủ lớn với bộ hoán vị này để in ra tiếp theo.

Cách làm : ta nhìn vào 4 số cuối của bộ hoán vị (3, 2, 6, 5, 4, 1), đang được xếp theo thứ tự giảm dần. Điều này có nghĩa là dù bạn xếp 4 số cuối kia (giữ nguyên vị trí 2 số đầu) theo thứ tự nào đi chăng nữa thì cũng sẽ thu được 1 bộ hoán vị nhỏ hơn bộ hoán vị đang có. Suy ra không thỏa mãn vì bộ hoán vị liệt kê sau cần lớn hơn bộ hoán vị trước nó.

Từ đó, để thu được 1 bộ hoán vị mới lớn hơn bộ hoán vị hiện tại ta cần xếp lại vị trí của 5 số cuối (3, 26, 5, 4, 1). Nhưng điều cần nhớ là bộ hoán vị sinh ra sau không chỉ cần lớn hơn mà còn cần vừa đủ lớn hơn so với bộ hoán vị trước nó. Và để được 1 bộ hoán vị mới thỏa mãn, ta cần chọn trong bốn số cuối một số vừa đủ lớn hơn số 2. Đó là số 4.

(Chọn trong bốn số cuối mà không chọn các số khác, trong trường hợp này là  số 3 vì nếu đổi chỗ 2 và 3 sẽ được ngay 1 hoán vị mới bé hơn hoán vị hiện tại. Trường hợp khác thì sẽ không thỏa mãn tính vừa đủ lớn.)

Tiếp theo, khi chọn được số 4, ta sẽ đổi chỗ số 4 và số 2, rồi đảo ngược toàn bộ chuỗi 4 số cuối lại.

(3, 2, 6, 5, 4, 1)  ----đổi chỗ 4 và 2--> (3, 4, 6, 5, 2, 1)  ----- đảo ngược 4 số cuối------>  (3, 4, 1, 2, 5, 6)

Lúc này ta sẽ được bộ (3, 4, 1, 2, 5, 6) là bộ vừa đủ lớn hơn (3, 2, 6, 5, 4, 1). nên bộ hoán vị (3, 4, 1, 2, 5, 6) là bộ tiếp theo được liệt kê ra ngay sau bộ (3, 2, 6, 5, 4, 1).

Ý tưởng viết chương trình :

- Xác đoạn cuối giảm dần dài nhất. ví dụ : (3, 2, 6, 5, 4, 1) thì 6, 5, 4, 1 là đoạn cuối cần tìm. Đi kèm với đoạn cuối này là số liền kề ngay trước đoạn cuối này. trong ví dụ trên thì là số 2.

- Xác định số nào là số thuộc đoạn cuối mà vừa đủ lớn hơn số liền kề trước đoạn cuối đó. ví dụ : (3, 2, 6, 5, 4, 1) thì số 4 là số thuộc đoạn cuối vừa đủ lớn hơn số 2 - số liền kề trước đoạn cuối giảm dần.

- Sau đó ta đổi chỗ hai số này. như ví dụ trên thì là đổi chỗ số 4 và số 2. khi đó đoạn cuối trở thành 6, 5, 2, 1, lúc này đảo ngược đoạn cuối mới này thành 1, 2, 5, 6.

- In ra bộ hoán vị mới : (3, 4, 1, 2, 5, 6). và tiếp tục tìm đoạn cuối giảm dần dài nhất mới. Cứ thế khi nào đến cuối in ra bộ hoán vị có dạng (6, 5, 4, 3, 2, 1) thì dừng lại vì đây là bộ cuối cùng. (bộ hoán vị (n, n-1, n-2, ...., 1) sẽ là bộ hoán vị cuối cùng cần in ra.)

Các bạn hãy tự code xem có thành công không nhé. Nếu chưa hiểu lắm hoặc cần trợ giúp thì hãy đọc lại hoặc xem hướng dẫn code và code mình viết bên dưới nhé.

Hướng dẫn viết chương trình :

- Khai báo n (kiểu int) sau đó yêu cầu người dùng nhập vào giá trị n.

- Khai báo một mảng số nguyên gồm n phần tử, mình gọi mảng này là A, rồi dùng vòng lặp chạy trong khoảng (0, n) để khởi tạo cho giá trị các phần tử trong mảng số nguyên A từ 1 đến n. và in ra bộ hoán bị đầu tiên này.

- Tạo một vòng lặp, duyệt từ phần tử A[n - 1] về phần từ A[0]. Khi đang duyệt nếy thấy phần tử A[i] > A[i-1] thực hiện bước dưới.

- Tạo một vòng lặp con bên trong vòng lặp ở bước trên, duyệt từ A[n - 1] đến A[i], khi đăng duyệt, nếu thấy 1 phần tử A[k] nào đó lớn hơn A[i-1] thì vòng lặp lại, tiến hành đổi chỗ A[k] và A[i-1].

- Sau đó đảo ngược chuỗi số từ vị trí A[n - 1] đến A[i]. Và tiến hành in ra bộ hoán vị này.

-  đặt i = n để vòng lặp mẹ được chạy lại từ đầu. (các bạn hãy thử nghĩ xem tại sao lại đặt là i = n thay vì i = n - 1 nhé.)

- Cứ thế chương trình sẽ tự dừng khi in ra đủ bộ hoán vị.

C Code Liệt kê hoán vị bằng phương pháp sinh :

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

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

    printf("\nCac bo hoan vi la :\n");

    // khoi tao mang gom n phan tu
    int mang[n];

    // gan gia tri cho cac phan tu cua mang va in ra bo hoan vi dau tien
    int i;
    for(i = 0; i < n; i++)
    {
        mang[i] = i + 1;
        printf("%d  ", mang[i]);
    }

    // xu ly de in ra cac bo hoan vi tiep theo
    for(i = n - 1; i > 0; i--)
    {
        // neu gap mang[i] > mang[i - 1]
        if(mang[i] > mang[i - 1])
        {
            int j;

            // tim trong bo cuoi giam dan phan tu vua du lon hon mang[i - 1] sau do swap.
            for(j = n - 1; j >= i; j--)
            {
                if(mang[j] > mang[i - 1])
                {
                    int temp = mang[j];
                    mang[j] = mang[i - 1];
                    mang[i - 1] = temp;
                    break;
                }
            }

            // dao nguoc bo cuoi
            for(j = n - 1; j > ((n - 1 + i) / 2); j--)
            {
                int temp = mang[i + n - 1 - j];
                mang[i + n - 1 - j] = mang[j];
                mang[j] = temp;
            }

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

            // i = n de khi thoat vong lap hien tai i-- thanh i = n - 1; va vong lap chay lai tu dau.
            i = n;
        }
    }

    getch();
    return 0;
}


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

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