Encuentra la n-ésima permutación lexicográfica de una string | conjunto 2

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. 

  1. ¡ El número total de permutaciones de una string formada por N caracteres (todos distintos) es N!
  2. 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 !) .
  3. ¡ 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *