数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究查找字符串在 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，请针对频率表中的下一个字符进行迭代，并反复修改计数，直到确定一个产生高于所需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
更新于：2020年7月25日
181次浏览
广告