Thứ tự từ điển

September 29, 2008 1053 words 5 minutes

/posts/2008/09-29-thu-tu-tu-dien/main.jpg

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, mò ra quy luật, từ đó có phương án implement tốt nhất.

Xét ví dụ bài toán phát biểu như sau:

Cho số nguyên dương n:
Với dãy a là một hoán vị các số nguyên từ 1 đến n, hãy tính thứ tự từ điển của hoán vị này.
Ngược lại, cho số tự nhiên k bé hơn n!, hãy tìm dãy a là hoán vị có số thứ tự k.
Lưu ý là thứ tự bắt đầu tính từ 0.

Trước hết là câu 1, 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 = [ 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! hoán vị.

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 một đơ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 cách tính như bước trên. Tuy nhiên có một điều cực kì quan trọng là trong dãy [ 5, 3, 1, 2 ] này, các số hạng không hề liên tiếp nhau: 1, 2, 3 rồi vọt lên 5. Do đó, ta 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 không quan niệm 5 là 4 ta sẽ vô tình xét thêm dạng [ 4, x, x, x ] dẫn đến kết quả sai. Để biết 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 2 suy ngược lại từ câu 1, 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ính phần tử đầu tiên của a, ta sẽ tìm xem dãy a thuộc dạng nào trong 5 dạng trên, chỉ cần lấy thương trong phép chia k cho 4!. Để tính phần tử tiếp theo của a, ta lại đi sâu vào dạng mới tìm được với số thứ tự là số dư trong phép chia k cho 4!. Cứ thế cho đến khi tính được phần tử cuối cùng của a.

Code minh họa:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#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();
}

2023/05/07 – Cập nhật code minh họa F# thần chưởng:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
let maxN = 10
let gt = Array.create maxN 1
for n = 1 to gt.Length-1 do gt[n] <- gt[n-1] * n
let count predicate = Seq.filter predicate >> Seq.length
let (</>) a b = a / b, a % b

let rec orderOf = function
    | [] -> 0
    | head :: tail ->
        (tail |> count ((>)head)) * gt[tail.Length] + orderOf tail

let listAt n order =
    let rec loop n order tokens =
        if n = 0 then []
        else
            let i, order = order </> gt[n-1]
            (tokens |> List.item i)
            :: loop (n-1) order (tokens |> List.removeAt i)
    loop n order [1..n]

// Test:
orderOf [ 4; 5; 3; 1; 2 ] // 94
listAt 5 94 // [ 4; 5; 3; 1; 2 ]