Перестановка, присутствующая в середине лексикографического порядка перестановок не более чем длины N, составляла целые числа до K.

Даны два положительных целых числа K и N , задача состоит в том, чтобы найти перестановку, присутствующую в середине всех перестановок не более чем длины N , состоящих из целых чисел из диапазона [1, K], расположенных лексикографически.

Примеры:

Input: K = 3, N = 2
Output: 2 1
Explanation: Lexicographical order of all possible permutations are:

1. {1}.
2. {1, 1}
3. {1, 2}
4. {1, 3}
5. {2}
6. {2, 1}
7. {2, 2}
8. {2, 3}
9. {3}
10. {3, 1}
11. {3, 2}
12. {3, 3}

Therefore, the middle lexicographically the smallest sequence is (N/2)^th(= 6^th) sequence, which is {2, 1}.

Input: K = 2, N = 4
Output: 1 2 2 2

Наивный подход: самый простой подход к решению данной проблемы — сгенерировать все возможные подпоследовательности длины [1, N] , состоящие из целых чисел из [1, K] . Сохраните эти элементы в массиве. После создания всех подпоследовательностей отсортируйте сохраненный список подпоследовательностей и напечатайте средний элемент списка.

Временная сложность: O( ^NK )
Вспомогательное пространство: O( ^NK )

Эффективный подход: описанный выше подход можно оптимизировать, проверив четность K , является ли K нечетным или четным, а затем найти среднюю лексикографически наименьшую последовательность соответственно. Выполните следующие шаги, чтобы решить проблему:

• Если значение K четное, то ровно половина последовательностей начинается с целого числа K/2 или меньше. Следовательно, результирующая последовательность — это K/2 , за которой следует (N — 1) вхождение K .
• Если значение K нечетное, то рассмотрим B как последовательность, содержащую N вхождений (K + 1)/2 .
  • Для последовательности X пусть f(X) будет такой последовательностью, что X _i в X заменено на (K + 1 − X _i ) .
  • Единственное исключение происходит для префиксов B .
• Начните с последовательности B и выполните следующие шаги (N – 1)/2 раза:
  • Если последний элемент текущей последовательности равен 1 , удалите его.
  • В противном случае уменьшите последний элемент на 1 и, пока последовательность содержит менее N элементов, вставьте K в конце последовательности B .
• После выполнения вышеуказанных шагов выведите полученную последовательность в массив B[] .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)