Khái niệm
Đối với một chuỗi đã cho có độ dài m chỉ chứa các bảng chữ cái viết thường, nhiệm vụ của chúng tôi là xác định hoán vị thứ n của chuỗi theo từ điển.
Đầu vào
str[] = "pqr", n = 3
Đầu ra
Result = "qpr"
Giải thích
Tất cả hoán vị có thể có theo thứ tự đã sắp xếp - pqr, prq, qpr, qrp, rpq, rqp
Đầu vào
str[] = "xyx", n = 2
Đầu ra
Result = "xyx"
Giải thích
Tất cả hoán vị có thể có theo thứ tự đã sắp xếp - xxy, xyx, yxx
Phương pháp
Ở đây chúng tôi sử dụng một số khái niệm Toán học để giải quyết vấn đề này.
Khái niệm này dựa trên các dữ kiện sau.
-
Ở đây, tổng số hoán vị của một chuỗi được tạo bởi N ký tự (tất cả đều khác biệt) là N!
-
Bây giờ, tổng số hoán vị của một chuỗi được tạo bởi N ký tự (trong trường hợp này tần số của ký tự C1 là M1, C2 là M2… và do đó tần số của ký tự Ck là Mk) là N! / (M1! * M2! *… .Mk!).
-
Một lần nữa, tổng số hoán vị của một chuỗi được tạo bởi N ký tự (tất cả đều khác biệt) sau khi sửa
Có thể thực hiện theo các bước dưới đây để đạt được giải pháp.
-
Lúc đầu, chúng tôi đếm tần số của tất cả các ký tự trong một mảng freq [].
-
Hiện tại từ ký tự nhỏ nhất đầu tiên có trong chuỗi (chỉ số nhỏ nhất i sao cho
-
freq [i]> 0), chúng tôi tính số hoán vị tối đa có thể có sau khi coi ký tự thứ i cụ thể đó là ký tự đầu tiên.
-
Người ta thấy rằng nếu giá trị tổng này cao hơn n đã cho, sau đó chúng tôi đặt ký tự đó làm ký tự đầu ra kết quả đầu tiên, freq giảm dần [i] và tiếp tục như vậy cho n-1 ký tự còn lại.
-
Mặt khác, người ta thấy rằng, nếu số lượng nhỏ hơn n được yêu cầu, hãy lặp lại cho ký tự tiếp theo trong bảng tần suất và sửa đổi số lượng nhiều lần cho đến khi chúng tôi xác định được một ký tự tạo ra số lượng cao hơn bắt buộc n.
Cần lưu ý rằng độ phức tạp về thời gian của phương pháp nêu trên là O (n), tức là thứ tự độ dài chuỗi.
Ví dụ
// C++ program to print
// n-th permutation
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int MAX_CHAR1 = 26;
const int MAX_FACT1 = 20;
ll fact1[MAX_FACT1];
// Shows utility for calculating factorials
void precomputeFactorials(){
fact1[0] = 1;
for (int i = 1; i < MAX_FACT1; i++)
fact1[i] = fact1[i - 1] * i;
}
// Shows function for nth permutation
void nPermute(char str1[], int n1){
precomputeFactorials();
// Indicates length of given string
int len1 = strlen(str1);
// Used to count frequencies of all
// characters
int freq1[MAX_CHAR1] = { 0 };
for (int i = 0; i < len1; i++)
freq1[str1[i] - 'a']++;
// Shows out1 string for output string
char out1[MAX_CHAR1];
//Used to iterate till sum equals n1
int sum1 = 0;
int k1 = 0;
// We umodify both n1 and sum1 in this
// loop.
while (sum1 != n1) {
sum1 = 0;
// Verify for characters present in freq1[]
for (int i = 0; i < MAX_CHAR1; i++) {
if (freq1[i] == 0)
continue;
// Remove character
freq1[i]--;
// Compute sum1 after fixing
// a particuar char
int xsum1 = fact1[len1 - 1 - k1];
for (int j = 0; j < MAX_CHAR1; j++)
xsum1 /= fact1[freq1[j]];
sum1 += xsum1;
// Now if sum1 > n1 fix that char as
// present char and modify sum1
// and required nth after fixing
// char at that position
if (sum1 >= n1) {
out1[k1++] = i + 'a';
n1 -= (sum1 - xsum1);
break;
}
// Now if sum1 < n1, add character back
if (sum1 < n1)
freq1[i]++;
}
}
// Now if sum1 == n1 means this
// char will provide its
// greatest permutation
// as nth permutation
for (int i = MAX_CHAR1 - 1;
k1 < len1 && i >= 0; i--)
if (freq1[i]) {
out1[k1++] = i + 'a';
freq1[i++]--;
}
// Used to append string termination
// character and print result
out1[k1] = '\0';
cout << out1;
}
// Driver program
int main(){
int n1 = 5;
char str1[] = "tutorialspoint";
// int n1 = 3;
// char str1[] = "pqr";
//int n1 = 2;
//char str1[] = "xyx";
nPermute(str1, n1);
return 0;
} Đầu ra
aiilnooprtsttu