Задача следующей комбинации (next permutation)

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

Ставится она так: есть набор (массив) элементов, чаще всего чисел, требуется найти следующей по порядку возрастания набор этих элементов.

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

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

Просматривая каждый раз массив с конца, мы находим место где i-й элемент меньше i + 1. Я назвал это место «точкой роста».

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

Например, в строке 4, точка роста — это элемент 3 (i = 1). Выбирая следующий по порядку (т.е. > 3) из хвоста [5, 2], мы имеем только один вариант — элемент 5. Этот элемент переходит на позицию i = 1, и у нас остается хвост из набора [3, 2]. Их мы сортируем, выстраивая по порядку [2, 3]. Так у нас получается следующая комбинация (шаг №5) — [1, 5, 2, 3].

Сортировка нужна, чтобы получить комбинацию чисел не просто больше предыдущей, а именно ближайшую следующую для заданной.

Если логика понятна, то перейдем к коду. Вариант на TS.

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

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

Задача: подсчета кол-ва возможных маршрутов

Июнь 25, 2023 г.

Решаем задачу с литкода №1575 Count All Possible Routes. Дан массив чисел, описывающий города. Указаны индексы стартового города (start) и города, куда нужно приехать (finish), а также запас топлива (fuel). Требуется найти кол-во путей, по которым ...

Читать

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

Июнь 7, 2023 г.

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

Читать

 

Комментарии к «Задача следующей комбинации (next permutation)»

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



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