Thứ tự từ điển

Các bài toán về thứ tự từ điển thì có cách giải thông thường là: viết ra giấy vài trường hợp, để ý phân tích, ra quy luật, từ đó có phương án cài đặt tốt nhất.

Bài toán phát biểu như sau:

Cho số nguyên dương n.
a. Cho dãy a[1], a[2], …, a[n] là 1 hoán vị các số nguyên từ 1 đến n. Hãy tìm thứ tự từ điển của hoán vị đó. Đánh số từ 1.
b. Ngược lại, cho số nguyên s (1 <= s <= n!), hãy tìm dãy a là hoán vị có số thứ tự s.

Trước hết là câu a, giải thích qua ví dụ thì dễ dàng hơn, chẳng hạn với n = 5 và dãy a là {4, 5, 3, 1, 2}. Tư tưởng là đi đếm xem có bao nhiêu hoán vị bé hơn a. Những hoán vị bé hơn a dễ thấy nhất có dạng:

{1, x, x, x, x}
{2, x, x, x, x}
{3, x, x, x, x}

trong đó mỗi dạng đều có số lượng hoán vị là 4! suy ra tổng cộng là 3 * 4!

Bây giờ xét đến dạng {4, x, x, x, x} bài toán có vẻ được lặp lại với kích thước giảm đi 1 đơn vị. Thật vậy, ta có thể bỏ số 4 để được dãy mới {5, 3, 1, 2} và quay lại như bước trên. Tuy nhiên có 1 điều cực kì quan trọng là trong dãy {5, 3, 1, 2} này, các số hạng ko hề liên tiếp nhau: 1, 2, 3 nhưng vọt lên 5. Do đó, bạn phải quan niệm số 5 là số 4 mới được. Để khi đó sẽ xét tiếp các dạng {1, x, x, x} {2, x, x, x} {3, x, x, x} Nếu ko quan niệm 5 là 4 bạn sẽ xét thêm dạng {4, x, x, x} dẫn đến kết quả sai. Để biết bạn phải quan niệm số 5 là số mấy, đơn giản đếm xem trong dãy {5, 3, 1, 2} có bao nhiêu số bé hơn 5.

Câu b suy ngược lại từ câu a, (vẫn lấy ví dụ n = 5) nhận xét rằng các hoán vị sẽ được sắp theo kiểu:

4! các hoán vị dạng {1, x, x, x, x}
4! các hoán vị dạng {2, x, x, x, x}
4! các hoán vị dạng {3, x, x, x, x}
4! các hoán vị dạng {4, x, x, x, x}
4! các hoán vị dạng {5, x, x, x, x}

Để tìm a[1], tức là tìm xem a thuộc dạng nào trong 5 dạng trên, chỉ cần lấy thương trong phép chia s cho 4! Để tìm a[2], ta lại đi sâu vào dạng mới tìm được, tính xem dãy a là thứ mấy trong dạng đó bằng cách lấy dư trong phép chia s cho 4! Cứ thế cho đến hết.

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

unsigned long gt[13];

void tinhgt() {
    gt[0] = 1;
    for (unsigned long i = 1; i < 13; i++)
        gt[i] = gt[i - 1] * i;
}

unsigned long thutu(int* a, int n) {
    unsigned long s = 0, i, j, k;
    for (i = 1; i <= n; i++) {
        j = 0;
        for (k = i + 1; k <= n; k++)
            if (a[k] < a[i]) j++;
        s += gt[n - i] * j;
    }
    return s + 1;
}

int* timday(unsigned long s, int n) {
    int* a = (int*)malloc(sizeof(int) * (n + 1));
    int* cx = (int*)malloc(sizeof(int) * (n + 1));
    int i, j, t;
    for (i = 1; i <= n; i++) cx[i] = 1;
    for (i = 1; i <= n; i++) {
        t = (s - 1) / gt[n - i] + 1;
        for (j = 1; j <= n; j++)
            if (cx[j]) {
                t--;
                if (t == 0) {
                    a[i] = j;
                    cx[j] = 0;
                    break;
                }
            }
        s = (s - 1) % gt[n - i] + 1;
    }
    return a;
}

void main() {
    tinhgt();
    clrscr();

    int i, n, a[13];

    printf("Nhap so nguyen duong <= 12, n = ");
    scanf("%d", &n);
    printf("\nCau a:\n");
    for (i = 1; i <= n; i++) {
        printf("Nhap a[%d] = ", i);
        scanf("%d", &a[i]);
    }
    printf("Ket qua = %lu", thutu(a, n));

    unsigned long s;
    printf("\n\nCau b:\n");
    printf("Nhap so nguyen duong <= %lu, s = ", gt[n]);
    scanf("%lu", &s);
    printf("Ket qua: ");
    int* b;
    b = timday(s, n);
    for (i = 1; i <= n; i++)
        printf("%d ", b[i]);

    getch();
}
Advertisements

2 thoughts on “Thứ tự từ điển

  1. em vẫn ko hiểu phần cuối câu a
    quan niệm 5 là 4
    tại sao như vậy
    nếu ko thì sao
    hi vọng anh chỉ rõ hơn
    em chỉ biết gõ pascal code c++ em ko hiểu

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s