Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Permutación lexicográfica

Encuentra la k-ésima permutación de unos caracteres distintos en orden lexicográfico.

Lo que aprenderás

  • Saltar bloques completos de permutaciones de una vez
  • Convertir un rango en una permutación
  • Trabajar con posiciones que empiezan en 0 y en 1

Problema

Ver original (inglés)

Haz la lista de todas las permutaciones de los caracteres de s en orden lexicográfico (el orden del diccionario). Para "abc" la lista es abc, acb, bac, bca, cab, cba. Devuelve la entrada número k, contando desde 1. Generar la lista completa es demasiado lento con 12 caracteres (479,001,600 permutaciones): cada bloque de permutaciones que empiezan por el mismo carácter tiene (longitud − 1)! elementos, así que puedes elegir los caracteres de uno en uno.

Implementa lexicographic_permutation(s, k).

Entrada

s: caracteres distintos en cualquier orden.

k: la posición en la lista ordenada, contando desde 1.

Salida

Devuelve la k-ésima permutación como cadena. Los caracteres se comparan por su código, así que las cifras van antes que las mayúsculas, y estas antes que las minúsculas.

Restricciones

1 ≤ s.length ≤ 12; todos los caracteres de s son distintos; 1 ≤ k ≤ s.length!

Ejemplos

Ejemplo 1
Entrada:
s = "abc"
k = 4

Salida esperada:
expected = "bca"
Entrada:
std::string s = "abc";
long long k = 4;

Salida esperada:
std::string expected = "bca";
Entrada:
string s = "abc";
long k = 4;

Salida esperada:
string expected = "bca";

Explicación

La lista es abc, acb, bac, bca, cab, cba, y la cuarta es "bca".

Ejemplo 2
Entrada:
s = "312"
k = 1

Salida esperada:
expected = "123"
Entrada:
std::string s = "312";
long long k = 1;

Salida esperada:
std::string expected = "123";
Entrada:
string s = "312";
long k = 1;

Salida esperada:
string expected = "123";

Explicación

La primera permutación son los caracteres ordenados: "123".

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Primero ordena los caracteres.

Pista 2

Cada elección del primer carácter abarca (longitud − 1)! permutaciones, así que al dividir k − 1 entre ese número sabes cuál elegir.

Pista 3

Quita el carácter elegido, quédate con el resto de la división y repite con los caracteres restantes.

Complejidad esperada

tiempo O(n²), espacio extra O(n)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.