Dada una string de longitud m que contiene solo letras en minúsculas. Necesitamos encontrar la n-ésima permutación del aliado lexicográfico de strings.
Ejemplos:
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
Enfoque ingenuo : encuentre lexicográficamente la n-ésima permutación usando STL .
Enfoque Eficiente: Concepto matemático para resolver este problema.
- ¡ El número total de permutaciones de una string formada por N caracteres (todos distintos) es N!
- El número total de permutación de una string formada por N caracteres (donde la frecuencia del carácter C1 es M1, C2 es M2… y por tanto la frecuencia del carácter Ck es Mk) es N!/(M1! * M2! *….Mk !) .
- ¡ El número total de permutaciones de una string formada por N caracteres (todos distintos) después de fijar el primer carácter es (N-1)!
Se pueden seguir los siguientes pasos para llegar a la solución.
- Cuente las frecuencias de todos los caracteres en una array.
- Ahora, a partir del primer carácter más pequeño presente en la string (índice más pequeño i tal que freq[i] > 0), calcule el número de permutaciones máximas posibles después de establecer ese i-ésimo carácter en particular como el primer carácter.
- Si este valor de suma es mayor que n dado, establezca ese carácter como el primer carácter de salida de resultado y disminuya freq[i]. Continúe igual para los caracteres n-1 restantes.
- Por otro lado, si el conteo es menor que el n requerido, itere hasta el siguiente carácter en la tabla de frecuencia y actualice el conteo una y otra vez hasta que encontremos un carácter que produzca un conteo mayor que el n requerido.
Implementació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
Python3
# 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.
Javascript
<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>
Producción
eegikqszu
Análisis de Complejidad:
- Complejidad temporal: O(n) , donde n es la n-ésima permutación.
- Complejidad espacial : O(n) donde n es el espacio necesario para almacenar la frecuencia.
Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA