Все задачи
Средне Решено: 0 Процент решений: 0%

Лексикографическая перестановка

Найдите k-ю перестановку различных символов в лексикографическом порядке.

Чему вы научитесь

  • Пропускать целые блоки перестановок за один шаг
  • Восстанавливать перестановку по её номеру
  • Работать с нумерацией с 0 и с 1

Условие

Выпишите все перестановки символов строки s в лексикографическом (словарном) порядке. Для «abc» список такой: abc, acb, bac, bca, cab, cba. Верните k-й элемент списка, считая с 1. Генерировать весь список для 12 символов слишком долго (479 001 600 перестановок). Но каждый блок перестановок с одним и тем же первым символом содержит (длина − 1)! элементов, поэтому символы можно выбирать по одному.

Реализуйте lexicographic_permutation(s, k).

Входные данные

s: различные символы в произвольном порядке.

k: позиция в отсортированном списке, считая с 1.

Выходные данные

Верните k-ю перестановку в виде строки. Символы сравниваются по их кодам, поэтому цифры идут раньше заглавных букв, а заглавные буквы раньше строчных.

Ограничения

1 ≤ s.length ≤ 12; все символы s различны; 1 ≤ k ≤ s.length!

Примеры

Пример 1
Ввод:
s = "abc"
k = 4

Ожидаемый вывод:
expected = "bca"
Ввод:
std::string s = "abc";
long long k = 4;

Ожидаемый вывод:
std::string expected = "bca";
Ввод:
string s = "abc";
long k = 4;

Ожидаемый вывод:
string expected = "bca";

Пояснение

Список: abc, acb, bac, bca, cab, cba, четвёртая перестановка - "bca".

Пример 2
Ввод:
s = "312"
k = 1

Ожидаемый вывод:
expected = "123"
Ввод:
std::string s = "312";
long long k = 1;

Ожидаемый вывод:
std::string expected = "123";
Ввод:
string s = "312";
long k = 1;

Ожидаемый вывод:
string expected = "123";

Пояснение

Первая перестановка - это символы в отсортированном порядке: "123".

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Сначала отсортируйте символы.

Подсказка 2

Каждый вариант первого символа покрывает (длина − 1)! перестановок, поэтому деление k − 1 на это число определяет первый символ.

Подсказка 3

Уберите выбранный символ, оставьте остаток от деления и повторите для оставшихся символов.

Ожидаемая сложность

время O(n²), доп. память O(n)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.