แนวคิด
สำหรับสตริงที่มีความยาว m ที่กำหนดซึ่งมีเฉพาะตัวอักษรพิมพ์เล็กเท่านั้น งานของเราที่จะกำหนดการเปลี่ยนแปลงลำดับที่ n ของสตริงตามพจนานุกรม
อินพุต
str[] = "pqr", n = 3
ผลลัพธ์
Result = "qpr"
คำอธิบาย
การเปลี่ยนแปลงที่เป็นไปได้ทั้งหมดในลำดับการเรียงลำดับ - pqr, prq, qpr, qrp, rpq, rqp
อินพุต
str[] = "xyx", n = 2
ผลลัพธ์
Result = "xyx"
คำอธิบาย
การเรียงสับเปลี่ยนที่เป็นไปได้ทั้งหมดในลำดับการจัดเรียง − xxy, xyx, yxx
วิธีการ
เราใช้แนวคิดทางคณิตศาสตร์ในการแก้ปัญหานี้
แนวคิดนี้มีพื้นฐานมาจากข้อเท็จจริงดังต่อไปนี้
-
ในที่นี้ จำนวนการเปลี่ยนแปลงทั้งหมดของสตริงที่สร้างโดยอักขระ N ตัว (ต่างกันทั้งหมด) คือ N!
-
ตอนนี้ จำนวนการเปลี่ยนแปลงทั้งหมดของสตริงที่สร้างโดยอักขระ N (ในกรณีนี้ ความถี่ของอักขระ C1 คือ M1, C2 คือ M2… และความถี่ของอักขระ Ck คือ Mk) คือ N!/(M1! * M2! *….Mk!).
-
อีกครั้ง จำนวนการเปลี่ยนแปลงทั้งหมดของสตริงที่สร้างโดยอักขระ N ตัว (ต่างกันทั้งหมด) หลังจากแก้ไข
สามารถทำตามขั้นตอนด้านล่างเพื่อเข้าถึงโซลูชัน
-
ขั้นแรก เรานับความถี่ของอักขระทั้งหมดในอาร์เรย์ freq[]
-
ปัจจุบันจากอักขระที่เล็กที่สุดตัวแรกที่มีอยู่ในสตริง (ดัชนีที่เล็กที่สุด i เช่นนั้น
-
freq[i]> 0) เราคำนวณจำนวนการเรียงสับเปลี่ยนสูงสุดที่เป็นไปได้หลังจากถือว่าอักขระ i-th นั้นเป็นอักขระตัวแรก
-
จะเห็นได้ว่าหากค่าผลรวมนี้สูงกว่าที่กำหนด n หลังจากนั้นเราตั้งค่าอักขระนั้นเป็นอักขระเอาต์พุตผลลัพธ์ตัวแรก ลด freq[i] และยังคงเหมือนเดิมสำหรับอักขระ n-1 ที่เหลือ
-
จะเห็นได้ว่าในทางกลับกัน หากการนับน้อยกว่า n ที่กำหนด ให้วนซ้ำสำหรับอักขระตัวถัดไปในตารางความถี่ และแก้ไขการนับครั้งแล้วครั้งเล่า จนกว่าเราจะกำหนดอักขระที่สร้างการนับที่สูงกว่า จำเป็น n.
ควรสังเกตว่าความซับซ้อนของเวลาของวิธีการดังกล่าวเป็น O(n) เช่น ลำดับของความยาวของสตริง
ตัวอย่าง
// 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;
} ผลลัพธ์
aiilnooprtsttu
