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>
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