Lexicográficamente n-ésima permutación de una string

Dada una string de longitud m que contiene solo letras en minúsculas. Tienes que encontrar la n-ésima permutación de la string lexicográficamente. 

Ejemplos:

Input : str[] = "abc", n = 3
Output : Result = "bac"
Explanation : All possible permutation in
sorted order: abc, acb, bac, bca, cab, cba

Input : str[] = "aba", n = 2
Output : Result = "aba"
Explanation : All possible permutation
in sorted order: aab, aba, baa

Requisito previo: las permutaciones de una string dada usando STL La idea detrás de la impresión de la permutación n-ésima es bastante simple, debemos usar STL (explicado en el enlace anterior) para encontrar la siguiente permutación y hacerlo hasta la permutación n-ésima. Después de la iteración n-ésima, debemos salir del ciclo y luego imprimir la string que es nuestra permutación n-ésima.

    long int i = 1;
    do
    {
        // check for nth iteration
        if (i == n)
            break;
       i++; // keep incrementing the iteration
    } while (next_permutation(str.begin(), str.end()));

    // print string after nth iteration
   print str;

Implementación:

// C++ program to print nth permutation with
// using next_permute()
#include <bits/stdc++.h>
using namespace std;
 
// Function to print nth permutation
// using next_permute()
void nPermute(string str, long int n)
{
    // Sort the string in lexicographically
    // ascending order
    sort(str.begin(), str.end());
 
    // Keep iterating until
    // we reach nth position
    long int i = 1;
    do {
        // check for nth iteration
        if (i == n)
            break;
 
        i++;
    } while (next_permutation(str.begin(), str.end()));
 
    // print string after nth iteration
    cout << str;
}
 
// Driver code
int main()
{
    string str = "GEEKSFORGEEKS";
    long int n = 100;
    nPermute(str, n);
    return 0;
}

// Java program to print nth permutation with
// using next_permute()
import java.util.*;
 
class GFG
{
 
// Function to print nth permutation
// using next_permute()
static void nPermute(char[] str, int n)
{
    // Sort the string in lexicographically
    // ascending order
    Arrays.sort(str);
 
    // Keep iterating until
    // we reach nth position
    int i = 1;
    do {
        // check for nth iteration
        if (i == n)
            break;
 
        i++;
    } while (next_permutation(str));
 
    // print string after nth iteration
    System.out.println(String.valueOf(str));
}
 
static boolean next_permutation(char[] p)
{
    for (int a = p.length - 2; a >= 0; --a)
        if (p[a] < p[a + 1])
        for (int b = p.length - 1;; --b)
            if (p[b] > p[a])
            {
                char t = p[a];
                p[a] = p[b];
                p[b] = t;
                for (++a, b = p.length - 1; a < b; ++a, --b)
                {
                    t = p[a];
                    p[a] = p[b];
                    p[b] = t;
                }
                return true;
            }
    return false;
}
 
// Driver code
public static void main(String[] args)
{
    String str = "GEEKSFORGEEKS";
    int n = 100;
    nPermute(str.toCharArray(), n);
}
}
 
// This code contributed by Rajput-Ji

# Python3 program to print nth permutation
# with using next_permute()
 
# next_permutation method implementation
def next_permutation(L):
    n = len(L)
    i = n - 2
    while i >= 0 and L[i] >= L[i + 1]:
        i -= 1
 
    if i == -1:
        return False
 
    j = i + 1
    while j < n and L[j] > L[i]:
        j += 1
    j -= 1
 
    L[i], L[j] = L[j], L[i]
 
    left = i + 1
    right = n - 1
 
    while left < right:
        L[left], L[right] = L[right], L[left]
        left += 1
        right -= 1
 
    return True
 
# Function to print nth permutation
# using next_permute()
def nPermute(string, n):
    string = list(string)
    new_string = []
 
    # Sort the string in lexicographically
    # ascending order
    string.sort()
    j = 2
 
    # Keep iterating until
    # we reach nth position
    while next_permutation(string):
        new_string = string
 
        # check for nth iteration
        if j == n:
            break
        j += 1
 
    # print string after nth iteration
    print(''.join(new_string))
 
# Driver Code
if __name__ == "__main__":
    string = "GEEKSFORGEEKS"
    n = 100
    nPermute(string, n)
 
# This code is contributed by
# sanjeev2552

// C# program to print nth permutation with
// using next_permute()
using System;
 
class GFG
{
 
// Function to print nth permutation
// using next_permute()
static void nPermute(char[] str, int n)
{
    // Sort the string in lexicographically
    // ascending order
    Array.Sort(str);
 
    // Keep iterating until
    // we reach nth position
    int i = 1;
    do
    {
        // check for nth iteration
        if (i == n)
            break;
 
        i++;
    } while (next_permutation(str));
 
    // print string after nth iteration
    Console.WriteLine(String.Join("",str));
}
 
static bool next_permutation(char[] p)
{
    for (int a = p.Length - 2; a >= 0; --a)
        if (p[a] < p[a + 1])
        for (int b = p.Length - 1;; --b)
            if (p[b] > p[a])
            {
                char t = p[a];
                p[a] = p[b];
                p[b] = t;
                for (++a, b = p.Length - 1; a < b; ++a, --b)
                {
                    t = p[a];
                    p[a] = p[b];
                    p[b] = t;
                }
                return true;
            }
    return false;
}
 
// Driver code
public static void Main()
{
    String str = "GEEKSFORGEEKS";
    int n = 100;
    nPermute(str.ToCharArray(), n);
}
}
 
/* This code contributed by PrinciRaj1992 */

EEEEFGGRKSOSK

Complejidad de Tiempo: O(n log n)
Espacio Auxiliar: O(1)

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

Este artículo es una contribución de Aarti_Rathi y 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.