資料結構
網路
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次瀏覽
廣告