查找字符串的第 n 次字典排列|集合 2
原文:https://www . geeksforgeeks . org/find-n-th-词典-排列-字符串-set-2/
给定一个长度为 m 的字符串，其中只包含小写字母。我们需要按字典顺序找到字符串的第 n 个排列。 例:
Input: str[] = "abc", n = 3
Output: Result = "bac"
All possible permutation in
sorted order: abc, acb, bac,
bca, cab, cba
Input: str[] = "aba", n = 2
Output: Result = "aba"
All possible permutation
in sorted order: aab, aba, baa
【天真方法】 : 使用 STL 查找词典第 n 个排列。 高效方法: 解决这个问题的数学概念。
- The total number of strings consisting of n characters (all different) is n!
- The total number of strings consisting of n characters (where the frequency of character C1 is M1, C2 is M2… so the frequency of character Ck is Mk) is n! /(M1！ * M2！ *….Mk！ ) 。
- After the first character is fixed, the total number of strings consisting of n characters (all different) is (n-1)!
可以遵循以下步骤来达成解决方案。
- 计算数组中所有字符的频率。
- 现在从字符串中出现的第一个最小字符(最小索引 I，使得 freq[i] > 0)开始，在将该特定的第 I 个字符设置为第一个字符后，计算可能的最大置换数。
- 如果该和值大于给定的 n，则将该字符设置为第一个结果输出字符，并递减 freq[i]。对剩余的 n-1 个字符继续相同的操作。
- 另一方面，如果计数小于所需的 n，则迭代查找频率表中的下一个字符，并一遍又一遍地更新计数，直到我们找到一个产生大于所需 n 的计数的字符。
C++
// C++ program to print
// n-th permutation
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int MAX_CHAR = 26;
const int MAX_FACT = 20;
ll fact[MAX_FACT];
// Utility for calculating factorials
void precomputeFactorials()
{
fact[0] = 1;
for (int i = 1; i < MAX_FACT; i++)
fact[i] = fact[i - 1] * i;
}
// Function for nth permutation
void nPermute(char str[], int n)
{
precomputeFactorials();
// Length of given string
int len = strlen(str);
// Count frequencies of all
// characters
int freq[MAX_CHAR] = { 0 };
for (int i = 0; i < len; i++)
freq[str[i] - 'a']++;
// Out string for output string
char out[MAX_CHAR];
// Iterate till sum equals n
int sum = 0;
int k = 0;
// We update both n and sum in this
// loop.
while (sum != n) {
sum = 0;
// Check for characters present in freq[]
for (int i = 0; i < MAX_CHAR; i++) {
if (freq[i] == 0)
continue;
// Remove character
freq[i]--;
// Calculate sum after fixing
// a particular char
int xsum = fact[len - 1 - k];
for (int j = 0; j < MAX_CHAR; j++)
xsum /= fact[freq[j]];
sum += xsum;
// if sum > n fix that char as
// present char and update sum
// and required nth after fixing
// char at that position
if (sum >= n) {
out[k++] = i + 'a';
n -= (sum - xsum);
break;
}
// if sum < n, add character back
if (sum < n)
freq[i]++;
}
}
// if sum == n means this
// char will provide its
// greatest permutation
// as nth permutation
for (int i = MAX_CHAR - 1;
k < len && i >= 0; i--)
if (freq[i]) {
out[k++] = i + 'a';
freq[i++]--;
}
// append string termination
// character and print result
out[k] = '\0';
cout << out;
}
// Driver program
int main()
{
int n = 2;
char str[] = "geeksquiz";
nPermute(str, n);
return 0;
}
Java 语言(一种计算机语言，尤用于创建网站)
// Java program to print
// n-th permutation
public class PermuteString {
final static int MAX_CHAR = 26;
final static int MAX_FACT = 20;
static long fact[] = new long[MAX_FACT];
// Utility for calculating factorial
static void precomputeFactorirals()
{
fact[0] = 1;
for (int i = 1; i < MAX_FACT; i++)
fact[i] = fact[i - 1] * i;
}
// Function for nth permutation
static void nPermute(String str, int n)
{
precomputeFactorirals();
// length of given string
int len = str.length();
// Count frequencies of all
// characters
int freq[] = new int[MAX_CHAR];
for (int i = 0; i < len; i++)
freq[str.charAt(i) - 'a']++;
// out string for output string
String out = "";
// Iterate till sum equals n
int sum = 10;
int k = 0;
// We update both n and sum
// in this loop.
while (sum >= n) {
// Check for characters
// present in freq[]
for (int i = 0; i < MAX_CHAR; i++) {
if (freq[i] == 0)
continue;
// Remove character
freq[i]--;
// calculate sum after fixing
// a particular char
sum = 0;
int xsum = (int)fact[len - 1 - k];
for (int j = 0; j < MAX_CHAR; j++)
xsum /= fact[freq[j]];
sum += xsum;
// if sum > n fix that char as
// present char and update sum
// and required nth after fixing
// char at that position
if (sum >= n) {
out += (char)(i + 'a');
k++;
n -= (sum - xsum);
break;
}
// if sum < n, add character back
if (sum < n)
freq[i]++;
}
}
// if sum == n means this
// char will provide its
// greatest permutation
// as nth permutation
for (int i = MAX_CHAR - 1;
k < len && i >= 0; i--)
if (freq[i] != 0) {
out += (char)(i + 'a');
freq[i++]--;
}
// append string termination
// character and print result
System.out.println(out);
}
// Driver program to test above method
public static void main(String[] args)
{
// TODO Auto-generated method stub
int n = 2;
String str = "geeksquiz";
nPermute(str, n);
}
}
// This code is contributed by Sumit Ghosh
Python 3
# Python3 program to print n-th permutation
MAX_CHAR = 26
MAX_FACT = 20
fact = [None] * (MAX_FACT)
# Utility for calculating factorials
def precomputeFactorials():
fact[0] = 1
for i in range(1, MAX_FACT):
fact[i] = fact[i - 1] * i
# Function for nth permutation
def nPermute(string, n):
precomputeFactorials()
# length of given string
length = len(string)
# Count frequencies of all
# characters
freq = [0] * (MAX_CHAR)
for i in range(0, length):
freq[ord(string[i]) - ord('a')] += 1
# out string for output string
out = [None] * (MAX_CHAR)
# iterate till sum equals n
Sum, k = 0, 0
# We update both n and sum in
# this loop.
while Sum != n:
Sum = 0
# check for characters present in freq[]
for i in range(0, MAX_CHAR):
if freq[i] == 0:
continue
# Remove character
freq[i] -= 1
# calculate sum after fixing
# a particular char
xsum = fact[length - 1 - k]
for j in range(0, MAX_CHAR):
xsum = xsum // fact[freq[j]]
Sum += xsum
# if sum > n fix that char as
# present char and update sum
# and required nth after fixing
# char at that position
if Sum >= n:
out[k] = chr(i + ord('a'))
n -= Sum - xsum
k += 1
break
# if sum < n, add character back
if Sum < n:
freq[i] += 1
# if sum == n means this char will provide
# its greatest permutation as nth permutation
i = MAX_CHAR-1
while k < length and i >= 0:
if freq[i]:
out[k] = chr(i + ord('a'))
freq[i] -= 1
i += 1
k += 1
i -= 1
# print result
print(''.join(out[:k]))
# Driver Code
if __name__ == "__main__":
n = 2
string = "geeksquiz"
nPermute(string, n)
# This code is contributed by Rituraj Jain
C
// C# program to print n-th permutation
using System;
public class GFG {
static int MAX_CHAR = 26;
static int MAX_FACT = 20;
static long[] fact = new long[MAX_FACT];
// utility for calculating factorial
static void precomputeFactorirals()
{
fact[0] = 1;
for (int i = 1; i < MAX_FACT; i++)
fact[i] = fact[i - 1] * i;
}
// function for nth permutation
static void nPermute(String str, int n)
{
precomputeFactorirals();
// length of given string
int len = str.Length;
// Count frequencies of all
// characters
int[] freq = new int[MAX_CHAR];
for (int i = 0; i < len; i++)
freq[str[i] - 'a']++;
// out string for output string
string ou = "";
// iterate till sum equals n
int sum = 10;
int k = 0;
// We update both n and sum in this
// loop.
while (sum >= n) {
// check for characters present in freq[]
for (int i = 0; i < MAX_CHAR; i++) {
if (freq[i] == 0)
continue;
// Remove character
freq[i]--;
// calculate sum after fixing
// a particular char
sum = 0;
int xsum = (int)fact[len - 1 - k];
for (int j = 0; j < MAX_CHAR; j++)
xsum /= (int)(fact[freq[j]]);
sum += xsum;
// if sum > n fix that char as
// present char and update sum
// and required nth after fixing
// char at that position
if (sum >= n) {
ou += (char)(i + 'a');
k++;
n -= (sum - xsum);
break;
}
// if sum < n, add character back
if (sum < n)
freq[i]++;
}
}
// if sum == n means this char will provide its
// greatest permutation as nth permutation
for (int i = MAX_CHAR - 1; k < len && i >= 0; i--)
if (freq[i] != 0) {
ou += (char)(i + 'a');
freq[i++]--;
}
// append string termination
// character and print result
Console.Write(ou);
}
// Driver program to test above method
public static void Main()
{
// TODO Auto-generated method stub
int n = 2;
String str = "geeksquiz";
nPermute(str, n);
}
}
// This code is contributed by nitin mittal.
java 描述语言
<script>
// Javascript program to print
// n-th permutation
let MAX_CHAR = 26;
let MAX_FACT = 20;
let fact=new Array(MAX_FACT);
// Utility for calculating factorial
function precomputeFactorirals()
{
fact[0] = 1;
for (let i = 1; i < MAX_FACT; i++)
fact[i] = fact[i - 1] * i;
}
// Function for nth permutation
function nPermute(str,n)
{
precomputeFactorirals();
// length of given string
let len = str.length;
// Count frequencies of all
// characters
let freq = new Array(MAX_CHAR);
for(let i=0;i<MAX_CHAR;i++)
{
freq[i]=0;
}
for (let i = 0; i < len; i++)
freq[str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
// out string for output string
let out = "";
// Iterate till sum equals n
let sum = 10;
let k = 0;
// We update both n and sum
// in this loop.
while (sum >= n) {
// Check for characters
// present in freq[]
for (let i = 0; i < MAX_CHAR; i++) {
if (freq[i] == 0)
continue;
// Remove character
freq[i]--;
// calculate sum after fixing
// a particular char
sum = 0;
let xsum = fact[len - 1 - k];
for (let j = 0; j < MAX_CHAR; j++)
xsum = Math.floor(xsum/fact[freq[j]]);
sum += xsum;
// if sum > n fix that char as
// present char and update sum
// and required nth after fixing
// char at that position
if (sum >= n) {
out += String.fromCharCode(i + 'a'.charCodeAt(0));
k++;
n -= (sum - xsum);
break;
}
// if sum < n, add character back
if (sum < n)
freq[i]++;
}
}
// if sum == n means this
// char will provide its
// greatest permutation
// as nth permutation
for (let i = MAX_CHAR - 1;
k < len && i >= 0; i--)
if (freq[i] != 0) {
out += String.fromCharCode(i + 'a'.charCodeAt(0));
freq[i++]--;
}
// append string termination
// character and print result
document.write(out);
}
// Driver program to test above method
// TODO Auto-generated method stub
let n = 2;
let str = "geeksquiz";
nPermute(str, n);
// This code is contributed by avanitrachhadiya2155
</script>
输出:
eegikqszu
复杂度分析:
- 时间复杂度: O(n)，其中 n 为第 n 次排列。
- 空间复杂度: O(n)其中 n 是存储频率所需的空间。
本文由Shivam Pradhan(anuj _ charm)供稿。如果你喜欢 GeeksforGeeks 并想投稿，你也可以使用write.geeksforgeeks.org写一篇文章或者把你的文章邮寄到 review-team@geeksforgeeks.org。看到你的文章出现在极客博客主页上，帮助其他极客。 如果发现有不正确的地方，或者想分享更多关于上述话题的信息，请写评论。
版权属于：月萌API www.moonapi.com，转载请注明出处
