Результат k-ой перестановки

Очередная задача с литкода (№60. Permutation Sequence). В общем случае формулируется так: дан набор элементов, требуется вернуть этот набор после k перестановок.

О чем идет речь? Если у нас есть n элементов, то мы можем получить n! перестановок с их участием. Например у нас есть числа 1, 2, 3. Существует всего 6 перестановок: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]].

В задаче говориться о k-ой по счету перестановке, т.е. порядок получения этих перестановок тоже важен.

Как генерируются комбинации

Надо разобраться в технике того, как вообще генерируются комбинации. Используя рекурсию, можно написать следующий алгоритм:

Функция перебора:

  1. У нас есть массив элементов, мы перебираем их один за другим.
  2. Если массив пуст — выходим из функции
  3. Для каждого элемента делаем следующее — изымаем элемент из массива, и вызываем функцию рекурсивно (1). Возвращаем элемент в массив.

Если добавить передачу в функцию параметра, содержащего изъятые элементы, то мы при достижении дна массива (когда он на очередном рекурсивном витке станет пуст) можем сказать, что в функцию была передана очередная комбинация.

Если мы перебираем массив от начала к концу, это гарантирует нам особый порядок элементов, а именно в порядке возрастания комбинаций относительно порядкового номера элементов в массиве. Т.е. именно так, как в приведенном выше примере.

Огнем и мечом (грубой силой), O(N!)

Имея этот багаж знаний, можно уже решить задачу в лоб. Перебрать все комбинации, и вернуть ту, что требуется.

В задаче говорится, что у нас n может быть от 1 до 9, т.е. комбинаций всего 362880. Т.е., нет проблемы для получения результата даже грубой силой за отведенное время.

Конечно, я прибегну к некоторым трюкам, например, не буду тратить вычислительное время на модификацию массивов (изъятие элемента и вставку обратно).

Это решение проходит критерии отбора на leetcode, конечно же с не самыми блестящими показателями.

Алгоритм 2, с затратами O(N)

Понятно, что есть O(N) решение для этой задачи, где мы находим непосредственно элементы для каждой позиции i в диапазоне от [1 … n]

Оптимизируем грубую силу

Забавно, но мы можем реализовать этот подход, обновив код первого алгоритма.

Если мы знаем, на какой итерации рекурсии мы находимся, то можно определить на сколько сильно влияет выбор очередного элемента. И если очередной элемент не позволяем нам достичь требуемого порядка k, то его можно пропустить.

Таким образом, рекурсия выродится до выбора правильной цифры и сведется, по сути, ко второму (быстрому) алгоритму.

Вот, что удалось получить с модифицированным алгоритмом.

Он вроде бы не должен быть на столько быстрее, видимо, мне повезло получить немного больше вычислительных ресурсов, чем обычно. Во втором алгоритме, правда есть плохая функция Array.splice(), но мы же вызываем её всего N раз.

Написать комментарий

Мало букафф? Читайте есчо !

Поиск выхода из лабиринта

Июнь 3, 2023 г.

Продолжаем разбор классических задач по программированию. На этот раз лабиринтовая задача, которая формулируется так - дан плоский лабиринт в виде двумерного массива, где стенка отмечена 1, а свободный участок как 0. Также дана начальная позиция игрока, ...

Читать

Игра в камни

Май 27, 2023 г.

Серия задач StoneGame на leetcode - образец игры, где требуется просчитать оптимальную стратегию. Выигрыш/проигрыш начинающего партию предопределен, и второй участник лишь может надеяться на ошибку первого. Но это не наш случай, т.к. по условию ...

Читать

 

Комментарии к «Результат k-ой перестановки»

Понравилась статья? Есть вопросы? - пишите в комментариях.



Комментарий: