Todos os desafios
Médio 0 resolvidos 0% de aceitação

Permutação lexicográfica

Encontre a k-ésima permutação de alguns caracteres distintos em ordem lexicográfica.

O que você vai aprender

  • Pular blocos inteiros de permutações de uma vez
  • Converter uma posição em uma permutação
  • Trabalhar com posições a partir de 0 e a partir de 1

Problema

Ver original (inglês)

Liste todas as permutações dos caracteres de s em ordem lexicográfica (a ordem do dicionário). Para "abc", a lista é abc, acb, bac, bca, cab, cba. Retorne a k-ésima entrada, contando a partir de 1. Gerar a lista inteira é lento demais para 12 caracteres (479 001 600 permutações): cada bloco de permutações que começa com o mesmo caractere tem (tamanho − 1)! entradas, então dá para escolher um caractere de cada vez.

Implemente lexicographic_permutation(s, k).

Entrada

s: caracteres distintos, em qualquer ordem.

k: a posição na lista ordenada, contando a partir de 1.

Saída

Retorne a k-ésima permutação como uma string. Os caracteres são comparados pelos seus códigos, então os dígitos vêm antes das letras maiúsculas, que vêm antes das minúsculas.

Restrições

1 ≤ s.length ≤ 12; todos os caracteres de s são distintos; 1 ≤ k ≤ s.length!

Exemplos

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

Saída esperada:
expected = "bca"
Entrada:
std::string s = "abc";
long long k = 4;

Saída esperada:
std::string expected = "bca";
Entrada:
string s = "abc";
long k = 4;

Saída esperada:
string expected = "bca";

Explicação

A lista é abc, acb, bac, bca, cab, cba, e a quarta é "bca".

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

Saída esperada:
expected = "123"
Entrada:
std::string s = "312";
long long k = 1;

Saída esperada:
std::string expected = "123";
Entrada:
string s = "312";
long k = 1;

Saída esperada:
string expected = "123";

Explicação

A primeira permutação é a dos caracteres em ordem: "123".

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Ordene os caracteres primeiro.

Dica 2

Cada escolha do primeiro caractere cobre (tamanho − 1)! permutações, então dividir k − 1 por esse número indica qual escolher.

Dica 3

Remova o caractere escolhido, guarde o resto da divisão e repita com os caracteres restantes.

Complexidade esperada

tempo O(n²), espaço extra O(n)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.