Задача следующей комбинации (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 г.

Разбираю задачу #200 с литкода, число островов (number of islands). Задан двумерный массив, в котором участки суши помечены как "1", а участки воды - как "0". Требуется подсчитать число получившихся островов. При этом считается, что участки суши образуют ...

Читать

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

Июль 5, 2023 г.

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

Читать

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

Июнь 7, 2023 г.

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

Читать

Классическая задача о размене монет

Январь 24, 2023 г.

Дана сумма amount и номиналы монет. Требуется разменять сумму минимальным набором монет. Если рассматривать набор монет, который используется в реальной жизни, т.е. [1коп, 5коп, 10коп, 50коп, 1р, 2р, 5р, 10р], то во-первых, решение всегда существует, ...

Читать
 

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

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



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