Результат 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 раз.

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

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

Задача: подсчитать варианты размена монет

Август 11, 2023 г.

Снова классика задач на перебор вариантов - есть номиналы монет, требуется найти все варианты размена указанной суммы. Число монет каждого номинала - не ...

Читать

Задача о неперекрывающихся интервалах

Июнь 7, 2023 г.

Задачи об интервалах легко решаются перебором. Но если элементов много, то нужно сообразить в каком порядке их лучше перебирать, чтобы избежать лишних вычислений. Формулируется задача так: дан массив интервалов, каждый из которых определен двумя числами ...

Читать

 

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

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



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