컨셉
소문자 알파벳만 포함하는 길이가 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! *....맥!).
-
다시 말하지만, 수정 후 N 문자(모두 고유)에 의해 생성된 문자열의 총 순열 수
아래 단계에 따라 해결 방법을 찾을 수 있습니다.
-
처음에는 배열 freq[]에 있는 모든 문자의 빈도를 계산합니다.
-
현재 문자열에 있는 첫 번째 가장 작은 문자부터(
-
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