在C ++中查找字符串的第n个词法排列
概念
对于仅包含小写字母的长度为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个特殊字符视为第一个字符后，计算出最大排列数。
可以看出，如果该总和值大于给定的n，则此后将该字符设置为第一个结果输出字符，递减freq [i]，对于其余n-1字符继续相同。
可以看到，另一方面，如果计数小于所需的n，则对频率表中的下一个字符进行迭代，并一遍又一遍地修改计数，直到我们确定产生一个计数值大于计数值的字符为止。必填项
需要说明的是，上述方法的时间复杂度为O(n)，即字符串长度的顺序。
示例
// C++ program to print//第n个排列
#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];
//显示用于计算阶乘的实用程序
void precomputeFactorials(){
fact1[0] = 1;
for (int i = 1; i < MAX_FACT1; i++)
fact1[i] = fact1[i - 1] * i;
}
//显示第n个排列的功能
void nPermute(char str1[], int n1){
precomputeFactorials();
//指示给定字符串的长度
int len1 = strlen(str1);
//用于计数所有频率
//字符
int freq1[MAX_CHAR1] = { 0 };
for (int i = 0; i < len1; i++)
freq1[str1[i] - 'a']++;
//显示输出字符串中的1字符串
char out1[MAX_CHAR1];
//用于迭代直到总和等于n1-
int sum1 = 0;
int k1 = 0;
//我们在这里将n1和sum1统一
//循环。
while (sum1 != n1) {
sum1 = 0;
// Verify for字符 present in freq1[]
for (int i = 0; i < MAX_CHAR1; i++) {
if (freq1[i] == 0)
continue;
//删除字符
freq1[i]--;
//固定后计算sum1-
//特殊字符
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
//显示字符并修改sum1-
//和所需的第n定影后
//在该位置的字符
if (sum1 >= n1) {
out1[k1++] = i + 'a';
n1 -= (sum1 - xsum1);
break;
}
// Now if sum1 < n1, add character back
if (sum1 < n1)
freq1[i]++;
}
}
//现在，如果sum1 == n1意味着
//char将提供其
//最大排列
//作为第n个排列
for (int i = MAX_CHAR1 - 1;
k1 < len1 && i >= 0; i--)
if (freq1[i]) {
out1[k1++] = i + 'a';
freq1[i++]--;
}
//用于附加字符串终止
//字符和打印结果
out1[k1] = '\0';
cout << out1;
}
//驱动程序
int main(){
int n1 = 5;
char str1[] = "nhooo";
//int n1 = 3;
// char str1[] = "pqr";
//int n1 = 2;
//char str1[] = "xyx";
nPermute(str1, n1);
return 0;
}
输出结果
aiilnooprtsttu
以上是 在C ++中查找字符串的第n个词法排列 的全部内容， 来源链接： utcz.com/z/353423.html
