Tutte le sfide
Media 0 risolte 0% di accettazione

Permutazione lessicografica

Trova la k-esima permutazione di alcuni caratteri distinti in ordine lessicografico.

Cosa imparerai

  • Saltare in un colpo solo interi blocchi di permutazioni
  • Convertire un rango in una permutazione
  • Lavorare con posizioni a base 0 e a base 1

Problema

Elenca tutte le permutazioni dei caratteri di s in ordine lessicografico, come in un dizionario. Per «abc» la lista è abc, acb, bac, bca, cab, cba. Restituisci l'elemento in posizione k, contando da 1. Generare l'intera lista è troppo lento con 12 caratteri (479 001 600 permutazioni): ogni blocco di permutazioni che iniziano con lo stesso carattere contiene (lunghezza − 1)! elementi, quindi puoi scegliere un carattere alla volta.

Implementa lexicographic_permutation(s, k).

Input

s: caratteri distinti in un ordine qualsiasi.

k: la posizione nella lista ordinata, contando da 1.

Output

Restituisci la k-esima permutazione come stringa. I caratteri si confrontano in base al loro codice, quindi le cifre vengono prima delle lettere maiuscole, che a loro volta vengono prima delle minuscole.

Vincoli

1 ≤ s.length ≤ 12; tutti i caratteri di s sono distinti; 1 ≤ k ≤ s.length!

Esempi

Esempio 1
Input:
s = "abc"
k = 4

Output atteso:
expected = "bca"
Input:
std::string s = "abc";
long long k = 4;

Output atteso:
std::string expected = "bca";
Input:
string s = "abc";
long k = 4;

Output atteso:
string expected = "bca";

Spiegazione

La lista è abc, acb, bac, bca, cab, cba e la quarta è "bca".

Esempio 2
Input:
s = "312"
k = 1

Output atteso:
expected = "123"
Input:
std::string s = "312";
long long k = 1;

Output atteso:
std::string expected = "123";
Input:
string s = "312";
long k = 1;

Output atteso:
string expected = "123";

Spiegazione

La prima permutazione è formata dai caratteri in ordine crescente: "123".

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Per prima cosa ordina i caratteri.

Suggerimento 2

Ogni scelta del primo carattere copre (lunghezza − 1)! permutazioni, quindi dividendo k − 1 per questo numero trovi quale scegliere.

Suggerimento 3

Togli il carattere scelto, tieni il resto della divisione e ripeti con i caratteri rimasti.

Complessità attesa

tempo O(n²), spazio aggiuntivo O(n)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.