Quy hoạch động thứ tự từ điển
Nguời viết:
- Nguyễn Hải Nam
Reviewer:
- Đỗ Thị Hồng Ngát, Trần Gia Khánh
Giới thiệu
Quy hoạch động thứ tự từ điển là một phương pháp quan trọng trong lĩnh vực khoa học máy tính, đặc biệt trong việc sắp xếp và tổ chức dữ liệu. Phương pháp này cho phép tự động sắp xếp một danh sách các từ hoặc chuỗi ký tự theo thứ tự chữ cái, từ đó tạo ra một cấu trúc dễ tra cứu và sử dụng.
Quy trình hoạt động của quy hoạch động thứ tự từ điển bao gồm các bước như so sánh, hoán đổi và lặp lại cho đến khi danh sách được sắp xếp hoàn toàn. Phương pháp này không chỉ nâng cao hiệu quả trong việc tìm kiếm thông tin mà còn tiết kiệm thời gian và tài nguyên.
Điểm nổi bật của quy hoạch động là khả năng điều chỉnh linh hoạt theo các điều kiện khác nhau, giúp tối ưu hóa quá trình sắp xếp trong các ứng dụng thực tế. Nhờ vào quy hoạch động thứ tự từ điển, người dùng có thể dễ dàng truy cập và quản lý thông tin, từ đó nâng cao hiệu suất công việc trong nhiều lĩnh vực như giáo dục, thương mại điện tử và quản lý dữ liệu.
Kiến thức cần biết
Để đọc hiểu bài viết sau một cách hiệu quả, bạn đọc nên có sẵn các kiến thức về:
Phát biểu bài toán quy hoạch động thứ tự từ điển
Đây là một dạng vấn đề thường gặp khi bạn cần tìm phần tử thứ \(K\) trong quy hoạch động thứ tự từ điển khi chúng ta tạo ra một chuỗi dài \(L\) từ một tập hợp có \(n\) phần tử, chẳng hạn như A. Bây giờ, nếu bạn phải giải quyết nó một cách thủ công… Bạn sẽ làm như thế nào? Tôi sẽ để bạn một chút thời gian để suy nghĩ.
Giải pháp đơn giản nhất có thể là liệt kê tất cả các khả năng và sau đó sắp xếp theo thứ tự từ vựng để lấy bất kỳ vị trí nào. Tuy nhiên, làm điều này trong một bài toán lập trình thì không hiệu quả chút nào.\Vì vậy, một lần nữa chúng ta sẽ áp dụng phương pháp \(DP\) cho vấn đề này.
Chúng ta sẽ lấy một mảng \( dp[i][j] \) trong đó \( i \) biểu thị độ dài của mảng và \( j \) biểu thị ký tự mà chuỗi hiện tại bắt đầu từ. Trường hợp cơ sở phụ thuộc vào chuỗi. Đối với trường hợp tổng quát \( i=1 \), tức là với chuỗi có độ dài đơn vị, chúng ta sẽ lấy tất cả các phần tử của nó một cách dễ dàng (bất kỳ ký tự nào). Bây giờ chúng ta có thể định nghĩa đệ quy của mình như sau:
recurse(n, K);
String answer = "";
recurse(int len, int K)
{
if (len == 0)
return;
For(j,0,m-1)
{
if(K > d[len,j])
K -= d[len,j];
else
break;
}
answer += (char)('a'+j);
recurse(len-1, K);
}
Ok, vậy hãy để chúng ta hãy cố gắng hiểu phương pháp quy hoạch động thứ tự từ điển. Trong mỗi lần lặp, chúng ta cố gắng xác định ký tự đầu tiên của chuỗi kết quả bằng cách sử dụng cùng một lập luận toán học rằng tất cả các phần tử có độ ưu tiên thấp hơn trong ký tự đầu tiên sẽ xuất hiện sớm hơn.
Bài toán 1 quy hoạch động thứ tự từ điển ( tìm xâu thứ k)
Chúng ta sẽ xét tất cả các chuỗi có độ dài từ 1 đến n sử dụng các ký tự a, b, c, sao cho các chuỗi con “ab”, “bb”, “ca” bị cấm. Tìm phần tử K-th trong quy hoạch động thứ tự từ điển.
Giả sử \( d[i][j] \) là số lượng các chuỗi có độ dài \( i \) (1 đến n) bắt đầu bằng ký tự thứ \( j \) (0 đến \( m-1 \), với \( m = 3 \)).
Nếu chúng ta bắt đầu với ‘a’, thì chúng ta có thể có các chuỗi có độ dài \( i-1 \), bắt đầu với ‘a’ hoặc ‘c’ là \( d[i-1][0] \) hoặc \( d[i-1][2] \). Đây là cách chúng ta có:
\[ d[i][0] = d[i-1][0] + d[i-1][1] + d[i-1][2] \quad // ab bị cấm \] \[ d[i][1] = d[i-1][1] \quad // bb bị cấm \] \[ d[i][2] = d[i-1][0] + d[i-1][1] + d[i-1][2] \quad // ca bị cấm \]
Tính toán \( d[i][j] \) cho tất cả \( i \) và \( j \). Sau đó, chúng ta sẽ sử dụng code được cung cấp để tính toán phần tử K-th.
Code tham khảo:
#include <bits/stdc++.h>
using namespace std;
// Factorial
int fact(int n) {
int res = 1;
for (int i = 2; i <= n; i++) { res *= i; }
return res;
}
// A utility function to count
// smaller characters on right of arr[low]
int findSmallerInRight(string str, int low) {
int countRight = 0;
for (int i = low + 1; i < str.size(); ++i)
if (str[i] < str[low])
++countRight;
return countRight;
}
// A function to find rank of a string
// in all permutations of characters
int findRank(string str) {
int n = str.size();
int mul = fact(n);
int rank = 1;
int countRight;
for (int i = 0; i < n; ++i) {
mul /= (n - i);
// Count number of chars smaller than str[i]
// from str[i+1] to str[len-1]
countRight = findSmallerInRight(str, i);
rank += countRight * mul;
}
return rank;
}
int main() {
string str = "string";
cout << findRank(str);
return 0;
}
Bài toán 2 ( phát triển từ bài 1):
Tìm hoán vị K-th trong hoán vị quy hoạch động thứ tự từ điển. Số lượng hoán vị có độ dài \( p \) là \( p! \) (giai thừa của \( p \)). Trong số đó, số lượng hoán vị bắt đầu với mỗi ký tự là \( \frac{(p-1)!}{(p-1)!} \). Chúng ta sử dụng code tương tự để tính toán câu trả lời.
Cài đặt
List nums;
For(i,0,n-1)
nums.add(i);
// Using K - 1 helps in using modulo operator as given K is 1 based
recurse(n, K - 1);
String answer = "";
recurse(int len, int K)
{
if (len == 0)
return;
int j = K / (len-1)!;
answer += (char)('0'+nums.get(j));
// remove jth element as it is gone from permutation
nums.remove(j);
K %= (len-1)! ;
recurse(len-1, K);
}
Độ phức tạp về thời gian của cách cài đặt trên là \(.
Chú ý thêm
Quy hoạch động thứ tự từ điển là dạng quy hoạch động nâng cao cần biết những kiến thức cơ bản về quy hoạch động, nắm bắt được những dạng quy hoạch động cơ bản và có thể ứng dụng ở mức khá.
